栈与队列¶
stack¶
后进先出(Last In, First Out - LIFO),比如浏览器中的后退与前进、软件中的撤销与反撤销。
内置栈¶
在 Python 中没有内置的栈类,可以将 list 当作栈使用,并忽略与栈无关的操作,可以视为一种受限制的数组或链表。
# 初始化
stack: list[int] = []
# 入栈
stack.append(1)
stack.append(2)
# 出栈
stack.pop()
# 访问栈顶元素
stack[-1]
# 获取栈的长度
size: int = len(stack)
# 判断是否为空
is_empty: bool = len(stack) == 0
基于数组实现¶
class ArrayStack:
"""基于数组实现的栈"""
def __init__(self):
"""构造方法"""
self._stack: list[int] = []
def size(self) -> int:
"""获取栈的长度"""
return len(self._stack)
def is_empty(self) -> bool:
"""判断栈是否为空"""
return self._stack == []
def push(self, item: int):
"""入栈"""
self._stack.append(item)
def pop(self) -> int:
"""出栈"""
if self.is_empty():
raise IndexError("栈为空")
return self._stack.pop()
def peek(self) -> int:
"""访问栈顶元素"""
if self.is_empty():
raise IndexError("栈为空")
return self._stack[-1]
def to_list(self) -> list[int]:
"""返回列表用于打印"""
return self._stack
基于链表实现¶
class LinkedListStack:
"""基于链表实现的栈"""
def __init__(self):
"""构造方法"""
self._peek: ListNode | None = None
self._size: int = 0
def size(self) -> int:
"""获取栈的长度"""
return self._size
def is_empty(self) -> bool:
"""判断栈是否为空"""
return not self._peek
def push(self, val: int):
"""入栈"""
node = ListNode(val)
node.next = self._peek
self._peek = node
self._size += 1
def pop(self) -> int:
"""出栈"""
num = self.peek()
self._peek = self._peek.next
self._size -= 1
return num
def peek(self) -> int:
"""访问栈顶元素"""
if self.is_empty():
raise IndexError("栈为空")
return self._peek.val
def to_list(self) -> list[int]:
"""转化为列表用于打印"""
arr = []
node = self._peek
while node:
arr.append(node.val)
node = node.next
arr.reverse()
return arr
queque¶
先进先出(First In, First Out - FIFO),比如打印机的任务队列、餐厅的出餐队列、购物订单队列
在 Python 中,虽然 queue.Queue()
是纯正的队列类,但不太好用,通常使用双向队列 deque
来当作队列使用
from collections import deque
# 初始化队列
que = deque()
# 入队
que.append(1)
que.append(3)
que.append(2)
que.append(5)
que.append(4)
# 出队
que.popleft()
# 访问队首元素
que[0]
# 获取队列长度
len(que)
double-ended queue¶
双向队列兼具栈与队列的逻辑,因此它可以实现这两者的所有应用场景,同时提供更高的自由度。
from collections import deque
# 初始化双向队列
deque = deque()
# 入队
deque.append(2) # 添加至队尾
deque.appendleft(3) # 添加至队首
# 访问元素
deque[0] # 队首元素
deque[-1] # 队尾元素
# 元素出队
deque.popleft() # 队首元素出队
deque.pop() # 队尾元素出队
# 获取双向队列的长度
len(deque)