栈与队列--python

一、栈

1、概述

一种先入后出的线性数据结构，类似于叠盘子，先放下的盘子得最后才能拿到。在最上面的盘子我们称为栈顶，在最底下的盘子我们称为栈底，将盘子添加到栈顶的操作叫做入栈，将盘子从栈顶抽走的操作叫做出栈。

将上述的盘子替换为元素，就是我们常说的栈了。

2、常见操作

常见的操作一般是入栈，出栈，访问栈顶元素。

# 初始化一个栈
stack: list[int] = []# 元素入栈
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)
stack.append(6)# 访问栈顶元素
peek: int = stack[-1]# 元素出栈
pop: int = stack.pop()# 获取栈的长度
size: int = len(stack)# 判空
is_empty: bool = len(stack) == 0

3、实现

因为栈遵循先入后出的原则，因此我们只能对栈顶的元素进行操作，包括添加、删除动作，而我们熟悉的两种数据结构都可以在任意的位置添加和删除元素，所以我们在模拟栈的时候，一般将其功能做一定的限制，将栈不能实现的功能给禁用掉，使他对外表现的逻辑符合栈的特性。

(一)链表实现

概述

在用链表实现时，我们可以用链表的头节点作为栈顶，尾节点作为栈底。入栈时，我们只需要将元素加入到链表头部，出栈时，我们只需要将元素从链表头部删除。

例如

class ListNode():def __init__(self, val):self.val = valself.next : ListNode | None = Noneself._size = 0# 基于链表实现栈的效果，链表需要提前定义好
class LinkListStack():def __init__(self):self._head: ListNode | None = Noneself._size: int = 0# 获得栈的长度def get_size(self) -> int:return self._size# 判断栈是否为空def is_empty(self) -> bool:return self._size == 0# 入栈def push_ele(self, val):node = ListNode(val)node._head = nodenode._size += 1# 栈顶元素def head(self):if self.is_empty():raise IndexError('栈为空，无元素')return self._head.val# 出栈def pop_ele(self):num = self.head()self._head = self._head.nextself._size -= 1return num# 转化为列表用于打印def to_list(self):arr = []node = self._headwhile node:arr.append(node.val)node = node.nextarr.reverse()return arr

(二)数组实现

概述

使用数组实现栈，可以将数组的结尾作为栈顶，入栈就是在尾部加入一个元素，出栈就是在尾部删除一个元素。

代码

# 数组实现
class ArrayStack():# 定义数组def __init__(self):self._stack: list[int] = []# 查询长度def size(self):return len(self._stack)# 判空def is_empty(self):return self.size() == 0# 入栈def get_push(self, item):self._stack.append(item)# 出栈def get_pop(self):if self.is_empty():raise IndexError('栈为空，无元素')return self._stack.pop()# 获得栈顶元素def head(self):if self.is_empty():raise IndexError('栈为空，无元素')return self._stack[-1]# 打印def to_list(self):return self._stack

二、队列

1、概述

队列是一种先入先出的线性数据结构，类似于我们生活中的排队，先排队的人先离开，后排队的人后离开。队伍的头部我们称为队首，队伍的尾部我们称为队尾，加入队伍尾部我们称为入队，删除队伍头部我们称为出队。

2、常见操作

一般是元素入队，元素出队，访问队首元素。

因为python中自带了双向队列，所以我们直接引用双向队列来模拟队列。

from collections import deque
# 初始化
que = deque()que.append(1)
que.append(2)
que.append(3)
que.append(4)
que.append(5)
# 队首元素
first = que[0]
# 元素出队
pop = que.popleft()
# 长度
size = len(que)
# 判空
is_empty = (len(que) == 0)

3、实现

(一)、链表实现

概述

链表的头结点表示队首，链表的尾结点表示队尾。队尾只能添加元素，队首只能删除元素。

代码

# 定义链表
class ListNode():def __init__(self, val):self.val = valself.next : ListNode | None = Noneself._size = 0# 链表实现
class LinkListQueue():def __init__(self):self._front: ListNode | None = Noneself._rear: ListNode | None = Noneself._size: int = 0# 获取长度def size(self):return self._size# 判空def is_empty(self):return self._size == 0# 入队def get_push(self, num):# 在尾结点后加node = ListNode(num)# 如果本身是空的，则头尾都指向该元素if self._front is None:self._front = nodeself._rear = node# 如果队列不是空，则加到尾结点else:self._rear.next = nodeself._rear = nodeself._size += 1# 出队def get_pop(self):num = self.head()self._front = self._front.nextself._size -= 1return num# 队首元素def head(self):if self.is_empty():raise IndexError('队列为空')# 转为列表输出def to_list(self):queue = []tmp = self._frontwhile self._front:queue.append(tmp.val)tmp = tmp.nextreturn queue

(二)数组实现

概述

数组删除元素不如链表方便，时间复杂度在O(n)，我们可以采用一种取巧的方式来避免这种情况，也就是设置两个指针，front和rear，分别指向队列的首个元素和最后一个元素。这样的话可以实现在删除时，通过直接移动队首指针，不体现删除元素的方式来模拟队列。

代码

class ArrayQueue():def __init__(self, size):self._nums: list[int] = [0] * sizeself._front: int = 0self._size: int = 0# 获取队列的容量def how_many(self):return self._size# 获取队列的长度def size(self):return self._size# 判空def is_empty(self):return self._size == 0# 入队def get_push(self, num):if self._size == self.how_many():raise IndexError('队列已经满了嗷~')rear = (self._front + self._size) % self.how_many()self._nums[rear] = numself._size += 1# 出队def get_pop(self):num = self.head()self._front = (self._front + 1) % self.how_many()self._size -= 1return num# 获得队首def head(self):if self.is_empty():raise IndexError('队列是空的嗷~')return self._nums[self._front]# 输出def to_list(self):res = [0] * self.size()j = self._frontfor i in range(self.size()):res[i] = self._nums[(j % self.how_many())]j += 1return res

三、双向队列

1、概述

队列中我们只能，对队列的队首做删除，对队尾做添加动作，而双向队列更加灵活，可以对队首或者队尾做删除或者添加动作。

2、常见操作

获取队首元素，获取队尾元素，删除队首元素，删除队尾元素，增加队首元素，增加队尾元素

# 双向队列
deq = deque()
# 添加至队尾
deq.append(1)       
deq.append(2)
# 添加至队首
deq.appendleft(3)   
deq.appendleft(4)
# 队首元素
front = deq[0]      
# 队尾元素
rear = deq[-1]      
# 队首出队
get_pop_front = deq.popleft() 
# 队尾出队
get_pop_rear = deq.pop()      
# 获取长度
lenth = len(deq)  
# 判空
is_empty: bool = (len(deq) == 0) 

3、实现

(一)、链表实现

# 双向队列--链表实现
# 创建链表结点
class ListNode():def __init__(self, val):self.val = valself.next : ListNode | None = Noneself.prev : ListNode | None = Noneself._size = 0class LinkListDeque():# 定义结点def __init__(self):self._front: ListNode | None = Noneself._rear: ListNode | None = Noneself._size = 0# 长度def size(self):return self._size# 判空def is_empty(self):return self._size == 0# 入队def get_push(self, num, is_front):node = ListNode(num)if self.is_empty():self._front = self._rear = nodeelif is_front:self._front.next = nodenode.next = self._frontself._front = nodeelse:self._rear.next = nodenode.prev = self._rearself._rear = nodeself._size += 1# 队首入队def get_push_front(self, num):self.get_push(num, True)# 队尾入队def get_push_rear(self, num):self.get_push(num, False)# 出队def get_pop(self, is_front):if self.is_empty():raise IndexError('双向队列为空~')if is_front:val = self._front.valfnext: ListNode | None = self._front.nextif fnext != None:fnext.prev = Noneself._front.next = Noneself._front = fnextelse:val = self._rear.valrprev: ListNode | None = self._rear.previf rprev != None:rprev.prev = Noneself._rear.next = Noneself._rear = rprevself._size -= 1return val# 队首出队def get_pop_front(self):return self.get_pop(True)# 队尾出队def get_pop_rear(self):return self.get_pop(False)# 获得队首def peek_front(self):if self.is_empty():raise IndexError('双向队列为空~')return self._front.val# 获得队尾def peek_rear(self):if self.is_empty():raise IndexError('双向队列为空~')return self._rear.val# 返回打印def to_array(self):node = self._frontres = [0] * self.size()for i in range(self.size()):res[i] = node.valnode = node.nextreturn res

(二)、数组实现

# 环形数组实现双向队列
class ArrayDeque():def __init__(self, how_many):self._nums = [0] * how_manyself._front = 0self._size = 0# 容量def how_many(self):return len(self._nums)# 大小def size(self):return self._size# 判空def is_empty(self):return self._size == 0# 获取当前位置def index(self, i):res = (i + self.how_many()) % self.how_many()return res# 加入队首def get_push_front(self, num):if self._size == self.how_many():print('双向队列满了~')returnself._front = self.index(self._front - 1)self._nums[self._front] = numself._size += 1# 加入队尾def get_push_rear(self, num):if self._size == self.how_many():print('双向队列满了~')returnrear = self.index(self._front + self._size)self._nums[rear] = numself._size += 1# 删除队首def get_pop_front(self):num = self.peek_front()self._front = self.index(self._front + 1)self._size -= 1return num# 删除队尾def get_pop_rear(self):num = self.peek_rear()self._size -= 1return num# 获得队首def peek_front(self):if self.is_empty():raise IndexError('双向队列为空~')return self._nums[self._front]# 获得队尾def peek_rear(self):if self.is_empty():raise IndexError('双向队列为空~')rear = self.index(self._front + self._size - 1)return self._nums[rear]# 做数组输出def to_array(self):res = []for i in range(self._size):res.append(self._nums[self.index(self._front + i)])return res