6. 栈

概念

栈（Stack） 是一种受限制的线性表，只允许在同一端（栈顶 top）进行插入和删除操作，遵循后进先出（LIFO, Last In First Out） 的原则。另一端称为栈底（bottom），栈底固定不可操作。

从逻辑结构上看，栈本质上是线性表，元素之间存在一对一的前驱后继关系，只是操作被限制在一端，因此它是一种操作受限的线性表。

根据存储结构不同，栈分为两种：

顺序栈（顺序存储）：用一段连续的内存空间（数组） 存储栈元素，用 top 指针记录栈顶位置。
- 优点：随机访问快、实现简单、Cache 友好。
- 缺点：容量固定，可能造成空间浪费或溢出，需要扩容或提前分配足够空间。
- 适用：栈大小可预估、对性能敏感的场合（如函数调用栈、表达式求值）。
链栈（链式存储）：用单链表实现，以链表头作为栈顶，入栈出栈相当于头插和头删。
- 优点：容量动态、不会因容量不足而溢出。
- 缺点：每个结点需要额外的指针空间，访问速度较慢。
- 适用：元素个数变化大、无法预估栈容量的场合。

链栈思想：链栈就是在链表的头部进行插入/删除。入栈 Push 相当于头插法插入新结点；出栈 Pop 相当于删除头结点。因为只在头部操作，所以时间复杂度都是 O(1)。

适用场景：函数调用与递归、括号匹配、表达式求值、浏览器/编辑器撤销、进制转换、深度优先搜索（DFS）等。

核心操作

操作	说明
`InitStack` 初始化	建立空栈，设置栈顶指针
`StackEmpty` 判空	判断栈是否为空
`StackFull` 判满	判断栈是否已满（顺序栈）
`Push` 进栈	在栈顶插入一个元素
`Pop` 出栈	删除栈顶元素并返回
`GetTop` 取栈顶	读取栈顶元素但不删除

复杂度分析

操作	顺序栈时间复杂度	链栈时间复杂度	空间复杂度
初始化	O(1)	O(1)	O(n) / O(1)
判空/判满	O(1)	O(1)	O(1)
Push 进栈	O(1)（扩容时为 O(n)）	O(1)	O(n)
Pop 出栈	O(1)	O(1)	O(1)
GetTop 取栈顶	O(1)	O(1)	O(1)

为什么： 栈的所有核心操作都只发生在栈顶这一端，顺序栈直接对数组下标操作，链栈直接操作头结点，都不需要移动其他元素，因此都是 O(1)。顺序栈在动态扩容时（如 C++ 的 std::vector 式扩容）需要把旧数组元素复制到新数组，单次扩容为 O(n)，但均摊下来仍接近 O(1)。

空间方面：顺序栈需要一整块连续空间 O(n)；链栈每个结点额外存储指针，总空间也是 O(n)，但按需分配、不会浪费。

语言实现

以下以顺序栈（数组实现）为主，四种语言各给出一种完整可运行实现，演示进栈、出栈、取栈顶等操作。

C

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

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];   // 用数组存放栈元素
    int top;             // 栈顶指针，-1 表示空栈
} SeqStack;

// 初始化栈
void InitStack(SeqStack *s) {
    s->top = -1;
}

// 判空
bool StackEmpty(SeqStack *s) {
    return s->top == -1;
}

// 判满
bool StackFull(SeqStack *s) {
    return s->top == MAXSIZE - 1;
}

// 进栈
bool Push(SeqStack *s, int x) {
    if (StackFull(s)) {
        printf("栈已满，无法进栈\n");
        return false;
    }
    s->data[++s->top] = x;   // 先自增 top 再存数据
    return true;
}

// 出栈
bool Pop(SeqStack *s, int *x) {
    if (StackEmpty(s)) {
        printf("栈为空，无法出栈\n");
        return false;
    }
    *x = s->data[s->top--];  // 先取数据再自减 top
    return true;
}

// 取栈顶（不删除）
bool GetTop(SeqStack *s, int *x) {
    if (StackEmpty(s)) {
        printf("栈为空，无栈顶元素\n");
        return false;
    }
    *x = s->data[s->top];
    return true;
}

int main() {
    SeqStack s;
    InitStack(&s);
    int x;

    // 进栈 1 2 3
    Push(&s, 1);
    Push(&s, 2);
    Push(&s, 3);

    // 取栈顶
    GetTop(&s, &x);
    printf("栈顶元素: %d\n", x);   // 3

    // 出栈，直到栈空
    while (!StackEmpty(&s)) {
        Pop(&s, &x);
        printf("出栈: %d\n", x);    // 3 2 1
    }
    return 0;
}

C++

#include <iostream>
#include <vector>
using namespace std;

// 顺序栈，用 vector 实现，支持动态扩容
template <typename T>
class SeqStack {
private:
    vector<T> data;   // 底层用 vector 存储
public:
    SeqStack() {}     // 初始化，空栈

    bool empty() const { return data.empty(); }

    // 进栈
    void push(const T &x) {
        data.push_back(x);   // 若容量不足会自动扩容
    }

    // 出栈
    bool pop(T &x) {
        if (empty()) return false;
        x = data.back();
        data.pop_back();
        return true;
    }

    // 取栈顶
    bool top(T &x) const {
        if (empty()) return false;
        x = data.back();
        return true;
    }

    size_t size() const { return data.size(); }
};

int main() {
    SeqStack<int> s;
    int x;

    s.push(1);
    s.push(2);
    s.push(3);

    s.top(x);
    cout << "栈顶元素: " << x << endl;   // 3
    cout << "栈大小: " << s.size() << endl;

    while (!s.empty()) {
        s.pop(x);
        cout << "出栈: " << x << endl;     // 3 2 1
    }
    return 0;
}

Java

import java.util.Arrays;

// 顺序栈，用数组实现，支持动态扩容
public class SeqStack<T> {
    private Object[] data;   // 存放栈元素
    private int top;         // 栈顶指针，-1 表示空栈
    private int capacity;

    public SeqStack() {
        capacity = 8;
        data = new Object[capacity];
        top = -1;
    }

    // 判空
    public boolean isEmpty() {
        return top == -1;
    }

    // 扩容：容量加倍并复制旧数据
    private void ensureCapacity() {
        if (top + 1 >= capacity) {
            capacity *= 2;
            data = Arrays.copyOf(data, capacity);
        }
    }

    // 进栈
    public void push(T x) {
        ensureCapacity();
        data[++top] = x;
    }

    // 出栈
    public T pop() {
        if (isEmpty()) throw new RuntimeException("栈为空");
        @SuppressWarnings("unchecked")
        T x = (T) data[top--];
        return x;
    }

    // 取栈顶
    public T peek() {
        if (isEmpty()) throw new RuntimeException("栈为空");
        @SuppressWarnings("unchecked")
        T x = (T) data[top];
        return x;
    }

    public int size() {
        return top + 1;
    }

    public static void main(String[] args) {
        SeqStack<Integer> s = new SeqStack<>();
        s.push(1);
        s.push(2);
        s.push(3);

        System.out.println("栈顶元素: " + s.peek());   // 3
        System.out.println("栈大小: " + s.size());

        while (!s.isEmpty()) {
            System.out.println("出栈: " + s.pop());      // 3 2 1
        }
    }
}

Python

# 顺序栈，用 Python 列表实现，天然支持动态扩容
class SeqStack:
    def __init__(self):
        # 初始化空栈，用列表作为底层存储
        self.data = []

    def is_empty(self):
        """判空"""
        return len(self.data) == 0

    def push(self, x):
        """进栈"""
        self.data.append(x)

    def pop(self):
        """出栈"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self.data.pop()

    def peek(self):
        """取栈顶（不删除）"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self.data[-1]

    def __len__(self):
        return len(self.data)

    def __str__(self):
        return f"SeqStack({self.data})"


if __name__ == "__main__":
    s = SeqStack()
    s.push(1)
    s.push(2)
    s.push(3)

    print("栈顶元素:", s.peek())    # 3
    print("栈大小:", len(s))

    while not s.is_empty():
        print("出栈:", s.pop())     # 3 2 1

栈的应用

括号匹配：遇到左括号进栈，遇到右括号与栈顶匹配。
表达式求值：中缀转后缀、利用栈计算后缀表达式。
函数调用：操作系统/语言运行时用系统栈保存调用现场（返回地址、局部变量）。
进制转换：十进制转二进制等，用栈逆序输出余数。
深度优先搜索（DFS）：显式用栈或递归（系统栈）实现。
浏览器的前进后退、编辑器的撤销：用双栈实现。

6.栈.md 8.9 KB Permalink Istoric Crud