栈¶

概述¶

栈（Stack）是一种**后进先出**（LIFO: Last In First Out）的线性数据结构。栈只允许在表的一端（称为栈顶，Top）进行插入和删除操作，另一端称为栈底（Bottom）。

栈的生活类比

想象一摞盘子：你只能从顶部放新盘子（push），也只能从顶部取盘子（pop）。最后放上去的盘子，最先被取走——这就是LIFO原则。

栈的抽象模型¶

栈的结构示意

5

↑ 栈顶 (Top) ← push/pop位置

4

3

2

1

栈底 (Bottom)

操作序列: push(1) → push(2) → push(3) → push(4) → push(5)

graph TB
    subgraph "栈的LIFO特性"
        A["push 1, 2, 3"] --> B["栈: [1, 2, 3]"]
        B --> C["pop → 返回 3"]
        C --> D["栈: [1, 2]"]
        D --> E["pop → 返回 2"]
        E --> F["栈: [1]"]
    end
    
    style C fill:#E8F5E9
    style E fill:#E8F5E9

栈的基本操作¶

操作	描述	时间复杂度
`push(x)`	将元素x压入栈顶	O(1)
`pop()`	弹出栈顶元素并返回	O(1)
`peek()/top()`	返回栈顶元素（不弹出）	O(1)
`isEmpty()`	判断栈是否为空	O(1)
`size()`	返回栈中元素个数	O(1)

栈的两种实现方式¶

数组实现 vs 链表实现¶

graph TB
    subgraph "数组实现（顺序栈）"
        A1["连续内存块"]
        A2["top指针记录栈顶位置"]
        A3["可能需要扩容"]
        A4["缓存友好"]
    end
    
    subgraph "链表实现（链式栈）"
        B1["分散内存节点"]
        B2["head指针指向栈顶"]
        B3["无需扩容，动态增长"]
        B4["每个节点额外指针开销"]
    end
    
    style A4 fill:#E8F5E9
    style B3 fill:#E8F5E9

特性	数组实现	链表实现
空间预分配	需要	不需要
扩容代价	O(n)复制	无
空间利用率	可能有浪费	每节点多一个指针
缓存友好	是 ✓	否 ✗
实现复杂度	简单	中等

数组实现（顺序栈）¶

结构设计与内存布局¶

栈的数组实现内存布局

初始状态 (top = -1):

0

1

2

3

4

↑ top = -1 (空栈)

push(10) 后 (top = 0):

10

0

1

2

3

4

↑ top = 0

push(20), push(30) 后 (top = 2):

10

20

30

0

1

2

3

4

↑ top = 2

完整代码实现¶

CC++PythonJavaGoRust

C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];  // 数据存储区
    int top;              // 栈顶指针（索引）
} ArrayStack;

// 初始化栈
void initStack(ArrayStack *s) {
    s->top = -1;  // -1表示空栈
}

// 判断栈是否为空
bool isEmpty(ArrayStack *s) {
    return s->top == -1;
}

// 判断栈是否已满
bool isFull(ArrayStack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈操作
void push(ArrayStack *s, int value) {
    if (isFull(s)) {
        printf("栈溢出 (Stack Overflow)!\n");
        return;
    }
    s->data[++s->top] = value;  // 先移动top，再存入元素
    printf("Push %d, top = %d\n", value, s->top);
}

// 出栈操作
int pop(ArrayStack *s) {
    if (isEmpty(s)) {
        printf("栈下溢 (Stack Underflow)!\n");
        return -1;
    }
    return s->data[s->top--];  // 先返回元素，再移动top
}

// 查看栈顶元素
int peek(ArrayStack *s) {
    if (isEmpty(s)) {
        printf("栈为空!\n");
        return -1;
    }
    return s->data[s->top];
}

// 获取栈的大小
int size(ArrayStack *s) {
    return s->top + 1;
}

// 打印栈内容
void printStack(ArrayStack *s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        return;
    }
    
    printf("栈内容（底→顶）: ");
    for (int i = 0; i <= s->top; i++) {
        printf("%d ", s->data[i]);
    }
    printf("\n");
}

C++
#include <vector>
#include <iostream>

class Stack {
private:
    std::vector<int> data;
    
public:
    // 入栈
    void push(int value) {
        data.push_back(value);
    }
    
    // 出栈
    int pop() {
        if (isEmpty()) {
            throw std::runtime_error("Stack Underflow");
        }
        int value = data.back();
        data.pop_back();
        return value;
    }
    
    // 查看栈顶
    int peek() {
        if (isEmpty()) {
            throw std::runtime_error("Stack is empty");
        }
        return data.back();
    }
    
    // 判空
    bool isEmpty() {
        return data.empty();
    }
    
    // 获取大小
    int size() {
        return data.size();
    }
};

Python
class Stack:
    """数组实现的栈"""
    def __init__(self, max_size=100):
        self.data = []
        self.max_size = max_size
    
    def push(self, value):
        """入栈"""
        if len(self.data) >= self.max_size:
            raise OverflowError("Stack Overflow")
        self.data.append(value)
    
    def pop(self):
        """出栈"""
        if not self.data:
            raise IndexError("Stack Underflow")
        return self.data.pop()
    
    def peek(self):
        """查看栈顶"""
        if not self.data:
            raise IndexError("Stack is empty")
        return self.data[-1]
    
    def is_empty(self):
        """判空"""
        return len(self.data) == 0
    
    def size(self):
        """获取大小"""
        return len(self.data)

Java
import java.util.ArrayList;
import java.util.EmptyStackException;

public class Stack {
    private ArrayList<Integer> data;
    private int maxSize;
    
    public Stack() {
        this(100);
    }
    
    public Stack(int maxSize) {
        this.data = new ArrayList<>();
        this.maxSize = maxSize;
    }
    
    public void push(int value) {
        if (data.size() >= maxSize) {
            throw new StackOverflowError("Stack Overflow");
        }
        data.add(value);
    }
    
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return data.remove(data.size() - 1);
    }
    
    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return data.get(data.size() - 1);
    }
    
    public boolean isEmpty() {
        return data.isEmpty();
    }
    
    public int size() {
        return data.size();
    }
}

Go
package main

import "errors"

// Stack 栈结构
type Stack struct {
    data    []int
    maxSize int
}

// NewStack 创建新栈
func NewStack(maxSize int) *Stack {
    return &Stack{
        data:    make([]int, 0, maxSize),
        maxSize: maxSize,
    }
}

// Push 入栈
func (s *Stack) Push(value int) error {
    if len(s.data) >= s.maxSize {
        return errors.New("stack overflow")
    }
    s.data = append(s.data, value)
    return nil
}

// Pop 出栈
func (s *Stack) Pop() (int, error) {
    if len(s.data) == 0 {
        return 0, errors.New("stack underflow")
    }
    value := s.data[len(s.data)-1]
    s.data = s.data[:len(s.data)-1]
    return value, nil
}

// Peek 查看栈顶
func (s *Stack) Peek() (int, error) {
    if len(s.data) == 0 {
        return 0, errors.New("stack is empty")
    }
    return s.data[len(s.data)-1], nil
}

// IsEmpty 判空
func (s *Stack) IsEmpty() bool {
    return len(s.data) == 0
}

// Size 获取大小
func (s *Stack) Size() int {
    return len(s.data)
}

Rust
pub struct Stack {
    data: Vec<i32>,
    max_size: usize,
}

impl Stack {
    pub fn new(max_size: usize) -> Self {
        Stack {
            data: Vec::with_capacity(max_size),
            max_size,
        }
    }
    
    pub fn push(&mut self, value: i32) -> Result<(), &'static str> {
        if self.data.len() >= self.max_size {
            return Err("Stack overflow");
        }
        self.data.push(value);
        Ok(())
    }
    
    pub fn pop(&mut self) -> Result<i32, &'static str> {
        self.data.pop().ok_or("Stack underflow")
    }
    
    pub fn peek(&self) -> Result<i32, &'static str> {
        self.data.last().copied().ok_or("Stack is empty")
    }
    
    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }
    
    pub fn size(&self) -> usize {
        self.data.len()
    }
}

操作示意¶

graph LR
    subgraph "Push操作"
        A1["检查是否满栈"] --> B1["top加1"]
        B1 --> C1["data[top] = value"]
    end
    
    subgraph "Pop操作"
        A2["检查是否空栈"] --> B2["返回data[top]"]
        B2 --> C2["top减1"]
    end
    
    style C1 fill:#E8F5E9
    style C2 fill:#E8F5E9

链表实现（链式栈）¶

结构设计¶

Text Only

链式栈结构:

栈顶指针 head
    ↓
┌──────┐    ┌──────┐    ┌──────┐
│  30  │───→│  20  │───→│  10  │───→ NULL
│ next │    │ next │    │ next │
└──────┘    └──────┘    └──────┘
  节点3       节点2       节点1

特点：栈顶在链表头部，push/pop都是O(1)

完整代码实现¶

C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 链表节点
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

// 链式栈
typedef struct {
    StackNode *top;   // 栈顶指针（链表头）
    int size;          // 栈大小
} LinkedStack;

// 初始化栈
void initLinkedStack(LinkedStack *s) {
    s->top = NULL;
    s->size = 0;
}

// 判断栈是否为空
bool isEmptyLS(LinkedStack *s) {
    return s->top == NULL;
}

// 入栈（头插法）
void pushLS(LinkedStack *s, int value) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    newNode->data = value;
    newNode->next = s->top;  // 新节点指向原栈顶
    s->top = newNode;         // 更新栈顶
    s->size++;
}

// 出栈
int popLS(LinkedStack *s) {
    if (isEmptyLS(s)) {
        printf("栈下溢!\n");
        return -1;
    }
    
    StackNode *temp = s->top;
    int value = temp->data;
    s->top = s->top->next;  // 栈顶下移
    free(temp);              // 释放节点
    s->size--;
    
    return value;
}

// 查看栈顶元素
int peekLS(LinkedStack *s) {
    if (isEmptyLS(s)) {
        printf("栈为空!\n");
        return -1;
    }
    return s->top->data;
}

// 释放栈内存
void freeLinkedStack(LinkedStack *s) {
    while (!isEmptyLS(s)) {
        popLS(s);
    }
}

栈的核心应用¶

1. 函数调用栈¶

graph TB
    subgraph "函数调用过程"
        A["main 调用 funcA"] --> B["push main的返回地址"]
        B --> C["funcA 调用 funcB"]
        C --> D["push funcA的返回地址"]
        D --> E["funcB 执行完毕"]
        E --> F["pop 返回funcA"]
        F --> G["funcA 执行完毕"]
        G --> H["pop 返回main"]
    end
    
    style F fill:#E8F5E9
    style H fill:#E8F5E9

Text Only

调用栈示意:

┌─────────────────┐
│ funcB 的栈帧    │ ← 栈顶
├─────────────────┤
│ funcA 的栈帧    │
├─────────────────┤
│ main 的栈帧     │ ← 栈底
└─────────────────┘

每个栈帧包含:
- 返回地址
- 局部变量
- 参数
- 保存的寄存器

2. 括号匹配¶

graph TB
    subgraph "括号匹配过程: [ 2 + 3 × 4"
        A["遇到 '[' → push"]
        B["栈: ['[']"]
        C["遇到 ']' → pop匹配"]
        D["栈: 空 ✓"]
    end
    
    A --> B --> C --> D
    
    style D fill:#E8F5E9

C
#include <string.h>
#include <stdbool.h>

// 括号匹配检测
bool isValidParentheses(char *s) {
    ArrayStack stack;
    initStack(&stack);
    
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        
        // 左括号入栈
        if (c == '(' || c == '[' || c == '{') {
            push(&stack, c);
        } 
        // 右括号匹配
        else if (c == ')' || c == ']' || c == '}') {
            if (isEmpty(&stack)) return false;  // 没有左括号可匹配
            
            char top = pop(&stack);
            // 检查匹配
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;  // 括号不匹配
            }
        }
    }
    
    return isEmpty(&stack);  // 栈必须为空才算完全匹配
}

3. 表达式求值¶

后缀表达式（逆波兰表达式）¶

Text Only

中缀表达式: 3 + 4 × 2 - 1
后缀表达式: 3 4 2 × + 1 -

后缀表达式求值过程:
┌────────────────────────────────────────┐
│ 输入: 3 4 2 × + 1 -                     │
├────────────────────────────────────────┤
│ 读入3:   栈: [3]                        │
│ 读入4:   栈: [3, 4]                     │
│ 读入2:   栈: [3, 4, 2]                  │
│ 读入×:   pop 2, 4; push 4×2=8; 栈: [3, 8]│
│ 读入+:   pop 8, 3; push 3+8=11; 栈: [11]│
│ 读入1:   栈: [11, 1]                    │
│ 读入-:   pop 1, 11; push 11-1=10        │
│ 结果: 10                                │
└────────────────────────────────────────┘

C
#include <ctype.h>
#include <string.h>

// 后缀表达式求值
int evaluatePostfix(char *expression) {
    ArrayStack stack;
    initStack(&stack);
    
    char *token = strtok(expression, " ");
    
    while (token != NULL) {
        // 如果是数字，入栈
        if (isdigit(token[0])) {
            push(&stack, atoi(token));
        } 
        // 如果是运算符，弹出两个操作数计算
        else {
            int b = pop(&stack);  // 第二个操作数（先弹出）
            int a = pop(&stack);  // 第一个操作数
            
            switch (token[0]) {
                case '+': push(&stack, a + b); break;
                case '-': push(&stack, a - b); break;
                case '*': push(&stack, a * b); break;
                case '/': push(&stack, a / b); break;
                case '^': push(&stack, pow(a, b)); break;
            }
        }
        token = strtok(NULL, " ");
    }
    
    return pop(&stack);
}

中缀转后缀¶

C
// 获取运算符优先级
int precedence(char op) {
    switch (op) {
        case '+':
        case '-': return 1;
        case '*':
        case '/': return 2;
        case '^': return 3;
        default: return 0;
    }
}

// 中缀表达式转后缀表达式
void infixToPostfix(char *infix, char *postfix) {
    ArrayStack stack;
    initStack(&stack);
    int j = 0;
    
    for (int i = 0; infix[i] != '\0'; i++) {
        char c = infix[i];
        
        // 数字直接输出
        if (isdigit(c) || isalpha(c)) {
            postfix[j++] = c;
        }
        // 左括号入栈
        else if (c == '(') {
            push(&stack, c);
        }
        // 右括号：弹出直到遇到左括号
        else if (c == ')') {
            while (!isEmpty(&stack) && peek(&stack) != '(') {
                postfix[j++] = pop(&stack);
            }
            pop(&stack);  // 弹出左括号
        }
        // 运算符：弹出更高或相等优先级的运算符
        else {
            while (!isEmpty(&stack) && 
                   precedence(peek(&stack)) >= precedence(c)) {
                postfix[j++] = pop(&stack);
            }
            push(&stack, c);
        }
    }
    
    // 弹出剩余运算符
    while (!isEmpty(&stack)) {
        postfix[j++] = pop(&stack);
    }
    postfix[j] = '\0';
}

4. 进制转换¶

graph TB
    subgraph "十进制1348转八进制"
        A["1348 ÷ 8 = 168 余 4"]
        B["168 ÷ 8 = 21 余 0"]
        C["21 ÷ 8 = 2 余 5"]
        D["2 ÷ 8 = 0 余 2"]
        E["栈: [4, 0, 5, 2]"]
        F["逆序输出: 2504"]
    end
    
    A --> B --> C --> D --> E --> F
    
    style F fill:#E8F5E9

C
void decimalToBase(int num, int base) {
    ArrayStack stack;
    initStack(&stack);
    
    // 不断除以base，余数入栈
    while (num > 0) {
        push(&stack, num % base);
        num /= base;
    }
    
    // 弹出所有余数，得到转换结果
    printf("转换结果: ");
    while (!isEmpty(&stack)) {
        int digit = pop(&stack);
        if (digit < 10) {
            printf("%d", digit);
        } else {
            printf("%c", 'A' + digit - 10);  // 16进制字母
        }
    }
    printf("\n");
}

5. 浏览器前进后退¶

C
typedef struct {
    ArrayStack backStack;      // 后退栈
    ArrayStack forwardStack;   // 前进栈
    char current[256];          // 当前页面
} Browser;

// 访问新页面
void visit(Browser *b, char *url) {
    push(&b->backStack, b->current[0]);  // 当前页面入后退栈
    strcpy(b->current, url);
    
    // 清空前进栈
    while (!isEmpty(&b->forwardStack)) {
        pop(&b->forwardStack);
    }
}

// 后退
void back(Browser *b) {
    if (!isEmpty(&b->backStack)) {
        push(&b->forwardStack, b->current[0]);  // 当前页面入前进栈
        b->current[0] = pop(&b->backStack);     // 从后退栈取页面
    }
}

// 前进
void forward(Browser *b) {
    if (!isEmpty(&b->forwardStack)) {
        push(&b->backStack, b->current[0]);     // 当前页面入后退栈
        b->current[0] = pop(&b->forwardStack);  // 从前进栈取页面
    }
}

6. 深度优先搜索（DFS）¶

C
// 使用栈实现的DFS（非递归版本）
void dfsStack(Graph *g, int start) {
    ArrayStack stack;
    initStack(&stack);
    bool visited[MAX_V] = {false};
    
    push(&stack, start);
    visited[start] = true;
    
    while (!isEmpty(&stack)) {
        int v = pop(&stack);
        printf("访问 %d\n", v);
        
        // 将未访问的邻居入栈
        for (int i = 0; i < g->n; i++) {
            if (g->adj[v][i] && !visited[i]) {
                push(&stack, i);
                visited[i] = true;
            }
        }
    }
}

C++ STL stack¶

C++
#include <stack>
#include <iostream>

int main() {
    std::stack<int> s;
    
    // 入栈
    s.push(1);
    s.push(2);
    s.push(3);
    
    // 查看栈顶
    std::cout << "栈顶: " << s.top() << std::endl;  // 3
    
    // 出栈
    s.pop();
    std::cout << "栈顶: " << s.top() << std::endl;  // 2
    
    // 栈大小和判空
    std::cout << "大小: " << s.size() << std::endl;   // 2
    std::cout << "是否为空: " << s.empty() << std::endl;  // 0 (false)
    
    return 0;
}

栈的变体¶

1. 最小栈（Min Stack）¶

在O(1)时间内获取栈中最小元素。

C
typedef struct {
    ArrayStack data;  // 主栈
    ArrayStack min;   // 辅助栈，存储每个位置的最小值
} MinStack;

void minStackPush(MinStack *ms, int value) {
    push(&ms->data, value);
    
    // 辅助栈存储当前位置的最小值
    if (isEmpty(&ms->min) || value <= peek(&ms->min)) {
        push(&ms->min, value);
    } else {
        push(&ms->min, peek(&ms->min));
    }
}

int getMin(MinStack *ms) {
    return peek(&ms->min);
}

2. 双端栈¶

使用一个数组实现两个栈。

Text Only

数组两端分别作为两个栈的栈底:

栈1 grows →        ← grows 栈2
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │   │   │   │   │ 6 │ 5 │
└───┴───┴───┴───┴───┴───┴───┴───┘
      ↑                 ↑
    top1              top2

常见问题与陷阱¶

1. 栈溢出¶

递归深度过大或栈空间不足：

C
// 危险：可能导致栈溢出
void infiniteRecursion() {
    infiniteRecursion();  // 无限递归
}

2. 栈下溢¶

对空栈执行pop操作：

C
ArrayStack s;
initStack(&s);
int x = pop(&s);  // 栈下溢！

空间复杂度¶

数组实现：O(n)，其中n为栈的最大容量
链表实现：O(n)，其中n为栈中元素个数

时间复杂度汇总¶

操作	时间复杂度	说明
push	O(1)	直接操作栈顶
pop	O(1)	直接操作栈顶
peek	O(1)	直接访问栈顶
isEmpty	O(1)	检查top指针
size	O(1)	返回计数器或top+1

参考资料¶

《算法导论》第10章 - 栈
《数据结构与算法分析》- Mark Allen Weiss
Stack (abstract data type) - Wikipedia
《CSAPP》第3章 - 运行时栈