一、栈（Stack）
栈是一种后进先出（LIFO）的线性数据结构。就像往手枪弹夹里装子弹时，子弹从弹夹口依次压入（入栈 push），先装的子弹会沉到弹夹底部；开枪时，最上面的那发子弹先被击发（出栈 pop）—— 最后装进去的子弹，最先被打出去；最先装的子弹，最后才被使用。这就是后进先出。
核心特性
1.栈只有一个操作端（称为「栈顶」），所有增删操作都在栈顶完成；
2.不支持随机访问（不能像列表一样通过索引取中间元素）；
核心操作
push：入栈（往栈顶加元素）；
pop：出栈（从栈顶删元素并返回）；
peek：查看栈顶元素（不删除）；
is_empty：判断栈是否为空。
代码实现
class Stack: # 基于列表结构实现栈 def __init__(self): self.stack = [] # 用列表存储栈元素 def push(self, item): # 入栈：将元素添加到栈顶 self.stack.append(item) def pop(self): # 出栈：删除并返回栈顶元素，栈空则打印栈空信息 if self.is_empty(): print('栈为空') return self.stack.pop() # pop默认删除最后一个元素（栈顶） def peek(self): # 查看栈顶元素（不删除） # 先判断栈是否为空，栈空则打印栈空信息 if self.is_empty(): print('栈为空') return self.stack[-1] # 返回栈顶元素 def is_empty(self): # 判断栈是否为空 return len(self.stack) == 0 def size(self): # 返回栈的大小 return len(self.stack) # 测试栈 s = Stack() s.push(1) # 栈：[1] s.push(2) # 栈：[1,2] s.push(3) # 栈：[1,2,3] print("栈顶元素：", s.peek()) # 输出：3 print("出栈：", s.pop()) # 输出：3 print("栈大小：", s.size()) # 输出：2 print("是否为空：", s.is_empty()) # 输出：False二、队列（Queue）
队列就像排队买奶茶：最先排队的人，最先买到奶茶；最后排队的人，最后买到 —— 这就是先进先出（First In First Out，FIFO）。
核心特性
有两个操作端：队首（只能用来出队）和 队尾（只能用来入队）；
元素从队尾进入，从队首离开；
核心操作
enqueue：入队（往队尾加元素）；
dequeue：出队（从队首删元素并返回）；
is_empty：判断队列是否为空；
size：返回队列大小。
代码实现
1.基于deque库实现队列
# python提供的库，deque双端队列 from collections import deque class Queue: # 基于deque的高性能队列 def __init__(self): self.queue = deque() def enqueue(self, item): # 入队：往队尾添加元素 self.queue.append(item) def dequeue(self): # 出队：从队首删除并返回元素，队空则打印提示信息 if self.is_empty(): print('队列为空') return self.queue.popleft() # 队首删除 def is_empty(self): # 判断队列是否为空 return len(self.queue) == 0 def size(self): # 获取队列的长度 return len(self.queue) # 测试队列 q = Queue() q.enqueue("用户1") # 队列：deque(['用户1']) q.enqueue("用户2") # 队列：deque(['用户1','用户2']) q.enqueue("用户3") # 队列：deque(['用户1','用户2','用户3']) print("出队：", q.dequeue()) # 输出：用户1（先进先出） print("队列大小：", q.size()) # 输出：22. 基于链表实现队列
class Node: # 链表节点 def __init__(self, data): self.data = data self.next = None class LinkedQueue: # 基于单链表实现的队列 def __init__(self): self.head = None # 队首（出队端） self.tail = None # 队尾（入队端） self._size = 0 def is_empty(self): # 判断队列是否为空 return self._size == 0 def enqueue(self, item): # 入队：在队尾添加节点 node = Node(item) if self.is_empty(): self.head = node self.tail = node else: self.tail.next = node self.tail = node self._size += 1 def dequeue(self): # 出队：移除并返回队首节点 if self.is_empty(): # 先判断是否为空，为空则打印提示信息 print('队列为空') current = self.head self.head = current.next # 如果队列只剩一个节点，出队后尾节点也要置空 if self.head is None: self.tail = None self._size -= 1 return current.data def front(self): # 查看队首元素 if self.is_empty(): print("队列为空，无法执行front操作") return self.head.data def size(self): # 查看队列长度 return self._size # 测试链表队列 if __name__ == "__main__": link_queue = LinkedQueue() link_queue.enqueue(1) link_queue.enqueue(2) print(link_queue.dequeue()) # 输出：1 print(link_queue.front()) # 输出：2三、循环队列（Circular Queue）
概念：
循环队列（也叫环形队列）是普通队列的优化版，解决了普通队列 “假溢出” 问题（队尾满但队首有空位），相当于 “循环链表” 在队列场景的应用。
核心特性
用固定大小的数组 / 列表实现，首尾相连形成循环；
用两个指针（front/rear）标记队首和队尾，避免元素移动；
适合 “固定容量” 的队列场景（如缓冲区、有限资源池）。
代码实现
class CircularQueue: # 循环队列（拥有固定的容量，避免了假溢出） def __init__(self, size): self.capacity = size # 队列最大容量 self.queue = [None] * size self.front = 0 # 队首指针（指向队首元素） self.rear = 0 # 队尾指针（指向队尾下一个位置） self.size = 0 # 当前元素个数 def is_empty(self): # 判断队列是否为空 return self.size == 0 def is_full(self): # 判断队列是否满 return self.size == self.capacity def enqueue(self, item): # 入队：队尾添加元素 # 添加元素，要先判断队满 if self.is_full(): print("循环队列已满!") self.queue[self.rear] = item self.rear = (self.rear + 1) % self.capacity # 循环移动指针 self.size += 1 def dequeue(self): # 出队：队首删除元素 # 删除元素，要先判断队空 if self.is_empty(): print("循环队列为空!") item = self.queue[self.front] self.queue[self.front] = None # 清空位置 self.front = (self.front + 1) % self.capacity # 循环移动指针 self.size -= 1 return item # 测试循环队列 cq = CircularQueue(3) # 容量3 cq.enqueue(1) cq.enqueue(2) cq.enqueue(3) # cq.enqueue(4) # 打印：循环队列已满！ print(cq.dequeue()) # 1 → 队首出队 cq.enqueue(4) # 队尾入队（利用空出的位置） print(cq.queue) # [None, 2, 3] → 实际存储（front=1, rear=0） print(cq.dequeue()) # 2 print(cq.dequeue()) # 3 print(cq.dequeue()) # 4 print(cq.is_empty()) # True
