4.1 栈的 LIFO 特性与 list 实现

栈是一种后进先出（Last In First Out, LIFO）的数据结构，就像一摞盘子，你只能从最上面拿盘子或者放盘子。在 Python 中，我们可以直接用内置的 list 来实现栈的基本操作。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
入栈	stack.append(item)	将元素添加到栈顶，时间复杂度 O(1)
出栈	stack.pop()	移除并返回栈顶元素，如果栈为空会抛出 IndexError
查看栈顶	stack[-1]	返回栈顶元素但不移除，需要先检查栈是否为空
判断空栈	len(stack) == 0 或 not stack	检查栈是否为空，避免对空栈进行 pop 或访问

下面是一个完整的栈实现示例：

# 定义一个简单的栈类
class Stack:
    def __init__(self):
        """初始化空栈"""
        self.items = []
    
    def push(self, item):
        """入栈操作 - 将元素添加到栈顶"""
        self.items.append(item)
    
    def pop(self):
        """出栈操作 - 移除并返回栈顶元素"""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.items.pop()
    
    def peek(self):
        """查看栈顶元素但不移除"""
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.items[-1]
    
    def is_empty(self):
        """判断栈是否为空"""
        return len(self.items) == 0
    
    def size(self):
        """返回栈中元素个数"""
        return len(self.items)

# 使用示例
try:
    # 创建栈实例
    stack = Stack()
    
    # 入栈操作
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print(f"栈大小: {stack.size()}")  # 输出: 栈大小: 3
    
    # 查看栈顶
    print(f"栈顶元素: {stack.peek()}")  # 输出: 栈顶元素: 3
    
    # 出栈操作
    print(f"出栈: {stack.pop()}")  # 输出: 出栈: 3
    print(f"出栈: {stack.pop()}")  # 输出: 出栈: 2
    
    # 检查是否为空
    print(f"栈是否为空: {stack.is_empty()}")  # 输出: 栈是否为空: False
    
except IndexError as e:
    print(f"错误: {e}")

使用 Python 的 list 实现栈非常简单高效，因为 append() 和 pop() 操作的时间复杂度都是 O(1)。不过要注意的是，虽然技术上你可以通过索引访问栈中的任意元素（比如 stack[0]），但这违背了栈的抽象数据类型原则，真正的栈应该只允许访问栈顶元素。

4.2 队列的 FIFO 特性与 collections.deque 实现

队列是一种先进先出（First In First Out, FIFO）的数据结构，就像排队买票，先来的人先买到票。在 Python 中，虽然可以用 list 实现队列，但效率不高，因为从列表头部删除元素的时间复杂度是 O(n)。更好的选择是使用 collections.deque。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
入队	queue.append(item)	将元素添加到队尾，时间复杂度 O(1)
出队	queue.popleft()	移除并返回队首元素，如果队列为空会抛出 IndexError
查看队首	queue[0]	返回队首元素但不移除，需要先检查队列是否为空
判断空队列	len(queue) == 0 或 not queue	检查队列是否为空

下面是使用 collections.deque 实现队列的示例：

from collections import deque

# 定义一个简单的队列类
class Queue:
    def __init__(self):
        """初始化空队列"""
        self.items = deque()
    
    def enqueue(self, item):
        """入队操作 - 将元素添加到队尾"""
        self.items.append(item)
    
    def dequeue(self):
        """出队操作 - 移除并返回队首元素"""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self.items.popleft()
    
    def front(self):
        """查看队首元素但不移除"""
        if self.is_empty():
            raise IndexError("front from empty queue")
        return self.items[0]
    
    def is_empty(self):
        """判断队列是否为空"""
        return len(self.items) == 0
    
    def size(self):
        """返回队列中元素个数"""
        return len(self.items)

# 使用示例
try:
    # 创建队列实例
    queue = Queue()
    
    # 入队操作
    queue.enqueue("Alice")
    queue.enqueue("Bob")
    queue.enqueue("Charlie")
    print(f"队列大小: {queue.size()}")  # 输出: 队列大小: 3
    
    # 查看队首
    print(f"队首元素: {queue.front()}")  # 输出: 队首元素: Alice
    
    # 出队操作
    print(f"出队: {queue.dequeue()}")  # 输出: 出队: Alice
    print(f"出队: {queue.dequeue()}")  # 输出: 出队: Bob
    
    # 检查是否为空
    print(f"队列是否为空: {queue.is_empty()}")  # 输出: 队列是否为空: False
    
except IndexError as e:
    print(f"错误: {e}")

collections.deque 是专门为高效实现队列操作而设计的，它的 append() 和 popleft() 操作都是 O(1) 时间复杂度，比使用普通 list 的 insert(0, item) 和 pop(0) 要高效得多。

4.3 单调栈：维护递增/递减序列

单调栈是一种特殊的栈，其中的元素保持单调递增或单调递减的顺序。这种数据结构在解决"下一个更大元素"、"柱状图中最大矩形"等问题时非常有用。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
维护单调递增栈	循环中比较栈顶与当前元素	当前元素小于等于栈顶时入栈，否则弹出栈顶直到满足条件
维护单调递减栈	循环中比较栈顶与当前元素	当前元素大于等于栈顶时入栈，否则弹出栈顶直到满足条件
获取每个元素的下一个更大元素	遍历数组，维护单调递减栈	栈中存储索引而非值，便于计算结果

下面是一个经典的"下一个更大元素"问题的解决方案：

def next_greater_element(nums):
    """
    找到数组中每个元素的下一个更大元素
    如果不存在则返回-1
    """
    n = len(nums)
    result = [-1] * n  # 初始化结果数组
    stack = []  # 单调递减栈，存储索引
    
    # 遍历数组两次处理循环情况（如果是循环数组）
    for i in range(n):
        # 当栈不为空且当前元素大于栈顶元素对应的值时
        while stack and nums[i] > nums[stack[-1]]:
            # 弹出栈顶索引，并设置其下一个更大元素为当前元素
            index = stack.pop()
            result[index] = nums[i]
        # 将当前索引入栈
        stack.append(i)
    
    return result

# 使用示例
try:
    nums = [2, 1, 2, 4, 3]
    result = next_greater_element(nums)
    print(f"原数组: {nums}")      # 输出: 原数组: [2, 1, 2, 4, 3]
    print(f"下一个更大元素: {result}")  # 输出: 下一个更大元素: [4, 2, 4, -1, -1]
    
    # 测试边界情况
    empty_nums = []
    empty_result = next_greater_element(empty_nums)
    print(f"空数组结果: {empty_result}")  # 输出: 空数组结果: []
    
except Exception as e:
    print(f"错误: {e}")

单调栈的核心思想是在遍历过程中维护栈的单调性。当我们遇到一个破坏单调性的元素时，就意味着找到了某些元素的"答案"。这种方法的时间复杂度是 O(n)，因为每个元素最多入栈和出栈各一次。

4.4 循环队列与双端队列（deque）

循环队列是一种特殊的队列，它的尾部连接到头部形成一个环形结构，这样可以更有效地利用固定大小的数组空间。而双端队列（deque）则允许在两端都进行插入和删除操作。

功能名称	实例调用方法	具体功能、注意事项、必需参数/可选参数
循环队列入队	(rear + 1) % capacity	需要处理队列满的判断，通常牺牲一个位置
循环队列出队	(front + 1) % capacity	更新队首指针
双端队列左端插入	deque.appendleft(item)	在队列左端添加元素
双端队列右端插入	deque.append(item)	在队列右端添加元素
双端队列两端删除	deque.popleft(), deque.pop()	分别从左右两端删除元素

首先看循环队列的实现：

class CircularQueue:
    def __init__(self, capacity):
        """初始化循环队列，capacity 为队列容量"""
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0  # 队首指针
        self.rear = 0   # 队尾指针
        self.size = 0   # 当前元素个数
    
    def enqueue(self, item):
        """入队操作"""
        if self.is_full():
            raise OverflowError("Queue is full")
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1
    
    def dequeue(self):
        """出队操作"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item
    
    def is_empty(self):
        """判断队列是否为空"""
        return self.size == 0
    
    def is_full(self):
        """判断队列是否已满"""
        return self.size == self.capacity
    
    def get_size(self):
        """获取队列当前大小"""
        return self.size

# 使用示例
try:
    # 创建容量为3的循环队列
    cq = CircularQueue(3)
    
    # 入队操作
    cq.enqueue(1)
    cq.enqueue(2)
    cq.enqueue(3)
    print(f"队列大小: {cq.get_size()}")  # 输出: 队列大小: 3
    
    # 队列已满，再次入队会报错
    try:
        cq.enqueue(4)
    except OverflowError as e:
        print(f"入队错误: {e}")  # 输出: 入队错误: Queue is full
    
    # 出队操作
    print(f"出队: {cq.dequeue()}")  # 输出: 出队: 1
    print(f"出队: {cq.dequeue()}")  # 输出: 出队: 2
    
    # 现在可以再次入队
    cq.enqueue(4)
    print(f"队列大小: {cq.get_size()}")  # 输出: 队列大小: 2
    
except Exception as e:
    print(f"错误: {e}")

再看双端队列的使用示例：

from collections import deque

# 双端队列的完整操作示例
def demonstrate_deque():
    """演示双端队列的各种操作"""
    dq = deque()
    
    # 右端插入
    dq.append(1)
    dq.append(2)
    print(f"右端插入后: {list(dq)}")  # 输出: 右端插入后: [1, 2]
    
    # 左端插入
    dq.appendleft(0)
    dq.appendleft(-1)
    print(f"左端插入后: {list(dq)}")  # 输出: 左端插入后: [-1, 0, 1, 2]
    
    # 右端删除
    right_item = dq.pop()
    print(f"右端删除: {right_item}, 队列: {list(dq)}")  # 输出: 右端删除: 2, 队列: [-1, 0, 1]
    
    # 左端删除
    left_item = dq.popleft()
    print(f"左端删除: {left_item}, 队列: {list(dq)}")  # 输出: 左端删除: -1, 队列: [0, 1]
    
    # 访问两端元素
    if dq:
        print(f"左端元素: {dq[0]}, 右端元素: {dq[-1]}")  # 输出: 左端元素: 0, 右端元素: 1
    
    return dq

# 运行演示
try:
    result_deque = demonstrate_deque()
    print(f"最终队列: {list(result_deque)}")  # 输出: 最终队列: [0, 1]
    
except Exception as e:
    print(f"错误: {e}")

循环队列通过模运算实现了空间的循环利用，避免了普通队列在出队后前端空间浪费的问题。而双端队列则提供了更大的灵活性，可以在两端进行操作，在滑动窗口、回文检查等场景中非常有用。