02-栈与队列

💡 核心结论

栈（Stack）

  • 特性：LIFO（后进先出），只能在栈顶操作

  • 操作：push、pop、peek 全部O(1)

  • 实现：数组栈（缓存友好）或链式栈（动态大小）

  • 应用：函数调用、表达式求值、括号匹配、撤销操作

  • 关键：限制访问顺序，强制后进先出

队列（Queue）

  • 特性：FIFO（先进先出），队尾入队头出

  • 操作：enqueue、dequeue、front 全部O(1)

  • 循环队列：用模运算实现，需要一个空位区分满和空

  • 应用：任务调度、BFS、消息队列、打印队列

  • 关键：公平性，先到先服务

实现对比

实现方式

优点

缺点

数组栈/队列

缓存友好、实现简单

需要扩容或固定大小

链式栈/队列

动态大小、无需扩容

指针开销、缓存不友好

📚 栈（Stack）

特点

  • LIFO（Last In First Out）后进先出

  • 只能在栈顶操作

  • 主要操作：push、pop、peek

应用场景

  • 函数调用栈

  • 表达式求值

  • 括号匹配

  • 浏览器历史记录（后退）

  • 撤销操作

时间复杂度

操作

复杂度

push

O(1)

pop

O(1)

peek

O(1)

search

O(n)

🎯 队列（Queue）

特点

  • FIFO（First In First Out）先进先出

  • 队尾入队，队头出队

  • 主要操作：enqueue、dequeue、front

应用场景

  • 任务调度

  • 广度优先搜索（BFS）

  • 消息队列

  • 打印队列

  • 操作系统进程调度

循环队列

[front] [1] [2] [3] [4] [rear]
         ↑              ↑
       front          rear

当rear到末尾时，从头开始
[3] [4] [rear] [front] [1] [2]
         ↑              ↑
       rear          front

时间复杂度

操作

复杂度

enqueue

O(1)

dequeue

O(1)

front

O(1)

search

O(n)

🔧 栈的实现方式

数组栈

优点：

  • 实现简单

  • 缓存友好

缺点：

  • 需要预分配空间或动态扩容

  • 扩容时需要拷贝

链式栈

优点：

  • 动态大小

  • 无需扩容

缺点：

  • 额外指针开销

  • 缓存不友好

🔧 队列的实现方式

数组队列（循环队列）

  • 使用模运算实现循环

  • 需要一个空位区分满和空

  • front == rear：队列为空

  • (rear + 1) % capacity == front：队列满

链式队列

  • 维护head和tail指针

  • 无需考虑满的情况

  • 动态大小

💡 经典问题

用栈实现括号匹配

def is_valid(s):
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in s:
        if char in pairs:
            stack.append(char)
        elif not stack or pairs[stack.pop()] != char:
            return False
    
    return not stack

# 测试
print(is_valid("()[]{}"))  # True
print(is_valid("([)]"))    # False

用栈计算后缀表达式

def eval_rpn(tokens):
    stack = []
    
    for token in tokens:
        if token in ['+', '-', '*', '/']:
            b = stack.pop()
            a = stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            else: stack.append(int(a / b))
        else:
            stack.append(int(token))
    
    return stack[0]

# 测试: ["2", "1", "+", "3", "*"] = (2 + 1) * 3 = 9
print(eval_rpn(["2", "1", "+", "3", "*"]))  # 9

用队列实现BFS

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 测试
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
bfs(graph, 'A')  # A B C D E F

单调栈

def next_greater_element(nums):
    """找每个元素右边第一个比它大的元素"""
    result = [-1] * len(nums)
    stack = []  # 单调递减栈
    
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            index = stack.pop()
            result[index] = nums[i]
        stack.append(i)
    
    return result

# 测试
print(next_greater_element([2, 1, 2, 4, 3]))  # [4, 2, 4, -1, -1]

📚 LeetCode练习

栈

队列

💡 最佳实践

  1. 选择合适的实现

    • 大小固定 → 数组实现

    • 大小动态 → 链表实现

  2. 异常处理

    • 检查空栈/空队列

    • 检查满队列

  3. 性能优化

    • 循环队列避免元素移动

    • 使用数组实现提高缓存命中

  4. 代码质量

    • 封装良好

    • 接口清晰

    • 异常安全

💻 完整代码实现

Python 实现

栈实现

 1"""
 2栈的实现：数组栈和链式栈
 3"""
 4
 5class ArrayStack:
 6    """基于数组的栈"""
 7    
 8    def __init__(self):
 9        self._data = []
10    
11    def push(self, val):
12        """入栈"""
13        self._data.append(val)
14    
15    def pop(self):
16        """出栈"""
17        if self.is_empty():
18            raise IndexError('pop from empty stack')
19        return self._data.pop()
20    
21    def peek(self):
22        """查看栈顶"""
23        if self.is_empty():
24            raise IndexError('peek from empty stack')
25        return self._data[-1]
26    
27    def is_empty(self):
28        """是否为空"""
29        return len(self._data) == 0
30    
31    def size(self):
32        """栈大小"""
33        return len(self._data)
34    
35    def __str__(self):
36        return f"Stack({self._data})"
37
38
39class LinkedStack:
40    """基于链表的栈"""
41    
42    class Node:
43        def __init__(self, val, next=None):
44            self.val = val
45            self.next = next
46    
47    def __init__(self):
48        self._top = None
49        self._size = 0
50    
51    def push(self, val):
52        """入栈"""
53        self._top = self.Node(val, self._top)
54        self._size += 1
55    
56    def pop(self):
57        """出栈"""
58        if self.is_empty():
59            raise IndexError('pop from empty stack')
60        val = self._top.val
61        self._top = self._top.next
62        self._size -= 1
63        return val
64    
65    def peek(self):
66        """查看栈顶"""
67        if self.is_empty():
68            raise IndexError('peek from empty stack')
69        return self._top.val
70    
71    def is_empty(self):
72        return self._size == 0
73    
74    def size(self):
75        return self._size
76
77
78if __name__ == '__main__':
79    print("=== 数组栈演示 ===\n")
80    stack = ArrayStack()
81    
82    for i in range(1, 4):
83        stack.push(i)
84        print(f"push({i}): {stack}")
85    
86    print(f"\npeek(): {stack.peek()}")
87    
88    while not stack.is_empty():
89        print(f"pop(): {stack.pop()}")
90    
91    print(f"\n栈是否为空: {stack.is_empty()}")
92

队列实现

  1"""
  2队列的实现：循环队列和链式队列
  3"""
  4
  5class CircularQueue:
  6    """循环队列（基于数组）"""
  7    
  8    def __init__(self, capacity=5):
  9        self._data = [None] * (capacity + 1)  # 多一个位置区分满和空
 10        self._front = 0
 11        self._rear = 0
 12        self._capacity = capacity + 1
 13    
 14    def enqueue(self, val):
 15        """入队"""
 16        if self.is_full():
 17            raise OverflowError('Queue is full')
 18        self._data[self._rear] = val
 19        self._rear = (self._rear + 1) % self._capacity
 20    
 21    def dequeue(self):
 22        """出队"""
 23        if self.is_empty():
 24            raise IndexError('dequeue from empty queue')
 25        val = self._data[self._front]
 26        self._front = (self._front + 1) % self._capacity
 27        return val
 28    
 29    def front(self):
 30        """查看队首"""
 31        if self.is_empty():
 32            raise IndexError('front from empty queue')
 33        return self._data[self._front]
 34    
 35    def is_empty(self):
 36        """是否为空"""
 37        return self._front == self._rear
 38    
 39    def is_full(self):
 40        """是否已满"""
 41        return (self._rear + 1) % self._capacity == self._front
 42    
 43    def size(self):
 44        """队列大小"""
 45        return (self._rear - self._front + self._capacity) % self._capacity
 46    
 47    def __str__(self):
 48        if self.is_empty():
 49            return "Queue([])"
 50        items = []
 51        i = self._front
 52        while i != self._rear:
 53            items.append(self._data[i])
 54            i = (i + 1) % self._capacity
 55        return f"Queue({items})"
 56
 57
 58class LinkedQueue:
 59    """链式队列"""
 60    
 61    class Node:
 62        def __init__(self, val, next=None):
 63            self.val = val
 64            self.next = next
 65    
 66    def __init__(self):
 67        self._head = None
 68        self._tail = None
 69        self._size = 0
 70    
 71    def enqueue(self, val):
 72        """入队"""
 73        new_node = self.Node(val)
 74        if self._tail is None:
 75            self._head = self._tail = new_node
 76        else:
 77            self._tail.next = new_node
 78            self._tail = new_node
 79        self._size += 1
 80    
 81    def dequeue(self):
 82        """出队"""
 83        if self.is_empty():
 84            raise IndexError('dequeue from empty queue')
 85        val = self._head.val
 86        self._head = self._head.next
 87        if self._head is None:
 88            self._tail = None
 89        self._size -= 1
 90        return val
 91    
 92    def front(self):
 93        """查看队首"""
 94        if self.is_empty():
 95            raise IndexError('front from empty queue')
 96        return self._head.val
 97    
 98    def is_empty(self):
 99        return self._size == 0
100    
101    def size(self):
102        return self._size
103
104
105# 双端队列
106class Deque:
107    """双端队列"""
108    
109    def __init__(self):
110        self._data = []
111    
112    def add_front(self, val):
113        """前端添加"""
114        self._data.insert(0, val)
115    
116    def add_rear(self, val):
117        """后端添加"""
118        self._data.append(val)
119    
120    def remove_front(self):
121        """前端删除"""
122        if self.is_empty():
123            raise IndexError('remove from empty deque')
124        return self._data.pop(0)
125    
126    def remove_rear(self):
127        """后端删除"""
128        if self.is_empty():
129            raise IndexError('remove from empty deque')
130        return self._data.pop()
131    
132    def is_empty(self):
133        return len(self._data) == 0
134
135
136if __name__ == '__main__':
137    print("=== 循环队列演示 ===\n")
138    queue = CircularQueue(5)
139    
140    print("入队: 1, 2, 3")
141    for i in range(1, 4):
142        queue.enqueue(i)
143        print(f"enqueue({i}): {queue}")
144    
145    print(f"\nfront(): {queue.front()}")
146    print(f"size(): {queue.size()}")
147    
148    print(f"\ndequeue(): {queue.dequeue()}")
149    print(f"队列: {queue}")
150    
151    print(f"\n入队: 4, 5")
152    queue.enqueue(4)
153    queue.enqueue(5)
154    print(f"队列: {queue}")
155

C++ 实现

栈实现

  1/**
  2 * 栈的实现：数组栈和链式栈
  3 */
  4
  5#include <iostream>
  6#include <stdexcept>
  7
  8// ========== 数组栈 ==========
  9template<typename T>
 10class ArrayStack {
 11private:
 12    T* data;
 13    int capacity;
 14    int top_index;
 15
 16public:
 17    ArrayStack(int cap = 10) : capacity(cap), top_index(-1) {
 18        data = new T[capacity];
 19    }
 20    
 21    ~ArrayStack() {
 22        delete[] data;
 23    }
 24    
 25    void push(const T& val) {
 26        if (top_index == capacity - 1) {
 27            // 扩容
 28            capacity *= 2;
 29            T* newData = new T[capacity];
 30            for (int i = 0; i <= top_index; i++) {
 31                newData[i] = data[i];
 32            }
 33            delete[] data;
 34            data = newData;
 35        }
 36        data[++top_index] = val;
 37    }
 38    
 39    T pop() {
 40        if (isEmpty()) {
 41            throw std::runtime_error("Pop from empty stack");
 42        }
 43        return data[top_index--];
 44    }
 45    
 46    T peek() const {
 47        if (isEmpty()) {
 48            throw std::runtime_error("Peek from empty stack");
 49        }
 50        return data[top_index];
 51    }
 52    
 53    bool isEmpty() const {
 54        return top_index == -1;
 55    }
 56    
 57    int size() const {
 58        return top_index + 1;
 59    }
 60    
 61    void print() const {
 62        std::cout << "Stack[";
 63        for (int i = 0; i <= top_index; i++) {
 64            std::cout << data[i];
 65            if (i < top_index) std::cout << ", ";
 66        }
 67        std::cout << "]" << std::endl;
 68    }
 69};
 70
 71
 72// ========== 链式栈 ==========
 73template<typename T>
 74class LinkedStack {
 75private:
 76    struct Node {
 77        T val;
 78        Node* next;
 79        Node(T v) : val(v), next(nullptr) {}
 80    };
 81    
 82    Node* top_node;
 83    int stack_size;
 84
 85public:
 86    LinkedStack() : top_node(nullptr), stack_size(0) {}
 87    
 88    ~LinkedStack() {
 89        while (!isEmpty()) {
 90            pop();
 91        }
 92    }
 93    
 94    void push(const T& val) {
 95        Node* newNode = new Node(val);
 96        newNode->next = top_node;
 97        top_node = newNode;
 98        stack_size++;
 99    }
100    
101    T pop() {
102        if (isEmpty()) {
103            throw std::runtime_error("Pop from empty stack");
104        }
105        Node* temp = top_node;
106        T val = temp->val;
107        top_node = top_node->next;
108        delete temp;
109        stack_size--;
110        return val;
111    }
112    
113    T peek() const {
114        if (isEmpty()) {
115            throw std::runtime_error("Peek from empty stack");
116        }
117        return top_node->val;
118    }
119    
120    bool isEmpty() const {
121        return stack_size == 0;
122    }
123    
124    int size() const {
125        return stack_size;
126    }
127};
128
129
130int main() {
131    std::cout << "=== 数组栈演示 ===" << std::endl << std::endl;
132    
133    ArrayStack<int> stack;
134    
135    std::cout << "入栈: 1, 2, 3" << std::endl;
136    for (int i = 1; i <= 3; i++) {
137        stack.push(i);
138        std::cout << "push(" << i << "): ";
139        stack.print();
140    }
141    
142    std::cout << "\npeek(): " << stack.peek() << std::endl;
143    std::cout << "size(): " << stack.size() << std::endl << std::endl;
144    
145    std::cout << "出栈:" << std::endl;
146    while (!stack.isEmpty()) {
147        std::cout << "pop(): " << stack.pop() << std::endl;
148    }
149    
150    std::cout << "\n栈是否为空: " << (stack.isEmpty() ? "是" : "否") << std::endl;
151    
152    return 0;
153}

队列实现

  1/**
  2 * 队列的实现：循环队列和链式队列
  3 */
  4
  5#include <iostream>
  6#include <stdexcept>
  7
  8// ========== 循环队列 ==========
  9template<typename T>
 10class CircularQueue {
 11private:
 12    T* data;
 13    int front_index;
 14    int rear_index;
 15    int capacity;
 16
 17public:
 18    CircularQueue(int cap = 5) : capacity(cap + 1), front_index(0), rear_index(0) {
 19        data = new T[capacity];
 20    }
 21    
 22    ~CircularQueue() {
 23        delete[] data;
 24    }
 25    
 26    void enqueue(const T& val) {
 27        if (isFull()) {
 28            throw std::runtime_error("Queue is full");
 29        }
 30        data[rear_index] = val;
 31        rear_index = (rear_index + 1) % capacity;
 32    }
 33    
 34    T dequeue() {
 35        if (isEmpty()) {
 36            throw std::runtime_error("Dequeue from empty queue");
 37        }
 38        T val = data[front_index];
 39        front_index = (front_index + 1) % capacity;
 40        return val;
 41    }
 42    
 43    T front() const {
 44        if (isEmpty()) {
 45            throw std::runtime_error("Front from empty queue");
 46        }
 47        return data[front_index];
 48    }
 49    
 50    bool isEmpty() const {
 51        return front_index == rear_index;
 52    }
 53    
 54    bool isFull() const {
 55        return (rear_index + 1) % capacity == front_index;
 56    }
 57    
 58    int size() const {
 59        return (rear_index - front_index + capacity) % capacity;
 60    }
 61    
 62    void print() const {
 63        std::cout << "Queue[";
 64        if (!isEmpty()) {
 65            int i = front_index;
 66            while (i != rear_index) {
 67                std::cout << data[i];
 68                i = (i + 1) % capacity;
 69                if (i != rear_index) std::cout << ", ";
 70            }
 71        }
 72        std::cout << "]" << std::endl;
 73    }
 74};
 75
 76
 77// ========== 链式队列 ==========
 78template<typename T>
 79class LinkedQueue {
 80private:
 81    struct Node {
 82        T val;
 83        Node* next;
 84        Node(T v) : val(v), next(nullptr) {}
 85    };
 86    
 87    Node* head;
 88    Node* tail;
 89    int queue_size;
 90
 91public:
 92    LinkedQueue() : head(nullptr), tail(nullptr), queue_size(0) {}
 93    
 94    ~LinkedQueue() {
 95        while (!isEmpty()) {
 96            dequeue();
 97        }
 98    }
 99    
100    void enqueue(const T& val) {
101        Node* newNode = new Node(val);
102        if (tail == nullptr) {
103            head = tail = newNode;
104        } else {
105            tail->next = newNode;
106            tail = newNode;
107        }
108        queue_size++;
109    }
110    
111    T dequeue() {
112        if (isEmpty()) {
113            throw std::runtime_error("Dequeue from empty queue");
114        }
115        Node* temp = head;
116        T val = temp->val;
117        head = head->next;
118        if (head == nullptr) {
119            tail = nullptr;
120        }
121        delete temp;
122        queue_size--;
123        return val;
124    }
125    
126    T front() const {
127        if (isEmpty()) {
128            throw std::runtime_error("Front from empty queue");
129        }
130        return head->val;
131    }
132    
133    bool isEmpty() const {
134        return queue_size == 0;
135    }
136    
137    int size() const {
138        return queue_size;
139    }
140};
141
142
143int main() {
144    std::cout << "=== 循环队列演示 ===" << std::endl << std::endl;
145    
146    CircularQueue<int> queue(5);
147    
148    std::cout << "入队: 1, 2, 3" << std::endl;
149    for (int i = 1; i <= 3; i++) {
150        queue.enqueue(i);
151        std::cout << "enqueue(" << i << "): ";
152        queue.print();
153    }
154    
155    std::cout << "\nfront(): " << queue.front() << std::endl;
156    std::cout << "size(): " << queue.size() << std::endl;
157    
158    std::cout << "\ndequeue(): " << queue.dequeue() << std::endl;
159    std::cout << "队列: ";
160    queue.print();
161    
162    std::cout << "\n入队: 4, 5" << std::endl;
163    queue.enqueue(4);
164    queue.enqueue(5);
165    std::cout << "队列: ";
166    queue.print();
167    
168    return 0;
169}