栈与队列 (Stack and Queue)

LeetCodeStackQueue栈队列数据结构

栈与队列 (Stack & Queue)

栈和队列是两种基础的线性数据结构，分别遵循LIFO（后进先出）和FIFO（先进先出）原则。

基础概念

栈（Stack）

操作示意:
Push 1:   | 1 |    Pop:    | 3 |    
         -----           | 2 |    
                        | 1 |    
Push 2:   | 2 |         -----    
         | 1 |                  
         -----                  

Push 3:   | 3 |    
         | 2 |    
         | 1 |    
         -----

基本操作:

  • push(x): 将元素x压入栈顶
  • pop(): 移除并返回栈顶元素
  • top(): 返回栈顶元素但不移除
  • isEmpty(): 检查栈是否为空

应用场景:

  • 函数调用栈
  • 表达式求值
  • 括号匹配
  • 深度优先搜索
  • 撤销操作

队列（Queue）

基本队列:
Enqueue:   1 -> 2 -> 3   Front: 1   Rear: 3
Dequeue:   2 -> 3        Front: 2   Rear: 3

循环队列:
              Front
                ↓
  [1] [2] [3] [4] [ ] [ ]
                      ↑
                    Rear

基本操作:

  • enqueue(x): 将元素x加入队尾
  • dequeue(): 移除并返回队首元素
  • front(): 返回队首元素但不移除
  • isEmpty(): 检查队列是否为空

应用场景:

  • 任务调度
  • 广度优先搜索
  • 缓冲区管理
  • 消息队列

经典问题

1. 有效的括号

LeetCode 20 - Valid Parentheses

使用栈匹配括号:

输入: ( { [ ] } )

步骤1: (         |  (  |
步骤2: ({        | ({  |
步骤3: ({[       |({[  |
步骤4: ({[]      |({   |  匹配 ]
步骤5: ({[]}     | (   |  匹配 }
步骤6: ({[]}）   |     |  匹配 )
def isValid(s):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or stack.pop() != pairs[char]:
                return False
    return len(stack) == 0

2. 用栈实现队列

LeetCode 232 - Implement Queue using Stacks

使用两个栈实现队列:

入队 3,2,1:
栈1: | 1 |    栈2: |   |
    | 2 |         |   |
    | 3 |         |   |
    -----         -----

出队操作时翻转到栈2:
栈1: |   |    栈2: | 3 |
    |   |         | 2 |
    |   |         | 1 |
    -----         -----
class MyQueue:
    def __init__(self):
        self.s1 = []  # 用于入队
        self.s2 = []  # 用于出队
        
    def push(self, x):
        self.s1.append(x)
        
    def pop(self):
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2.pop()

3. 滑动窗口最大值

LeetCode 239 - Sliding Window Maximum

使用双端队列（单调队列）:

数组: [1, 3, -1, -3, 5, 3, 6, 7]  窗口大小: 3

步骤1: [1  3  -1] -3  5  3  6  7    最大值: 3
       队列: [3, -1]

步骤2:  1 [3  -1  -3] 5  3  6  7    最大值: 3
       队列: [3, -1, -3]

步骤3:  1  3 [-1  -3  5] 3  6  7    最大值: 5
       队列: [5]

步骤4:  1  3  -1 [-3  5  3] 6  7    最大值: 5
       队列: [5, 3]
def maxSlidingWindow(nums, k):
    from collections import deque
    result = []
    q = deque()  # 存储下标
    
    for i in range(len(nums)):
        # 移除窗口左侧超出范围的元素
        if q and q[0] < i - k + 1:
            q.popleft()
            
        # 移除所有小于当前元素的值
        while q and nums[q[-1]] < nums[i]:
            q.pop()
            
        q.append(i)
        
        # 当窗口形成时添加结果
        if i >= k - 1:
            result.append(nums[q[0]])
            
    return result

4. 最小栈

LeetCode 155 - Min Stack

使用辅助栈跟踪最小值:

操作序列:
push(3): 主栈 |3|     最小栈 |3|
push(2): 主栈 |2|3|   最小栈 |2|3|
push(5): 主栈 |5|2|3| 最小栈 |2|2|3|
pop():   主栈 |2|3|   最小栈 |2|3|
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
        
    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
            
    def pop(self):
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()
            
    def top(self):
        return self.stack[-1]
        
    def getMin(self):
        return self.min_stack[-1]

高级主题

单调栈

单调队列

  • 用于维护滑动窗口中的最大/最小值
  • 队列元素保持单调性
  • 示例问题：上述滑动窗口最大值

优先队列（堆）

常见技巧

  1. 使用栈处理括号和嵌套结构
  2. 使用队列进行层次遍历
  3. 双栈实现队列，双队列实现栈
  4. 单调栈解决下一个更大元素
  5. 优先队列处理第K个元素

相关题目