03、栈

厨子大约 10 分钟数据结构算法基础面试题解析栈程序厨校招社招

哈喽，大家好，今天给大家介绍一下，非常常用的数据结构，栈，那按照惯例，我们举个生活中的例子，来引入栈

生活中的栈

栈是一种后进先出的数据结构。

大家可以想象以下场景：

叠盘子：

我们拿取时，会优先拿取最上面的盘子（那要是非得从中间抽，我也没办法🐶）

收作业：

老师会先改最后收取的作业

以上就是我们提到的后进先出

那下面我们来看一下，栈的定义吧

栈的定义

栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端叫做栈的顶（top），对栈的基本操作有 push(进栈)和 pop(出栈),前者相当于插入，后者则是删除最后插入的元素。

栈的另一个名字是 LIFO（后进先出）表。

普通的清空栈的操作和判断是否空栈的测试都是栈的操作指令系统的一部分，我们对栈能做的基本上也就是 push 和 pop 操作。

注：该图描述的模型只象征着 push 是输入操作，pop 是输出操作

下图表示进行若干操作后的一个抽象的栈。一般的模型是，存在某个元素位于栈顶，而该元素是唯一可见元素。

来简单总结一下

栈是一种线性数据结构，只允许在一端（称为栈顶）进行插入和删除操作。

核心特点：

后进先出（LIFO）
只能在栈顶操作
其他位置的元素无法直接访问

到这里，大家基本就有点了解，栈是怎么一回事了，下面我们来看一下，栈的基本操作

栈的基本操作

核心操作

操作	说明	时间复杂度
push(x)	将元素 x 压入栈顶	O(1)
pop()	删除栈顶元素并返回	O(1)
top()/peek()	查看栈顶元素（不删除）	O(1)
isEmpty()	判断栈是否为空	O(1)
size()	返回栈中元素个数	O(1)

操作示例

以下为上面视频的文字描述

栈的操作演示：

初始状态：空栈
Stack: []

1. push(10):
   Stack: [10]

2. push(20):
   Stack: [10, 20]

3. push(30):
   Stack: [10, 20, 30]

4. top():
   返回: 30
   Stack: [10, 20, 30]  （栈不变）

5. pop():
   返回: 30
   Stack: [10, 20]

6. push(40):
   Stack: [10, 20, 40]

7. pop():
   返回: 40
   Stack: [10, 20]

8. pop():
   返回: 20
   Stack: [10]

9. isEmpty():
   返回: false

10. pop():
    返回: 10
    Stack: []

11. isEmpty():
    返回: true

到这块大家基本就对，栈的各个函数，有一定的了解了，下面咱们看一下，栈的实现方式

栈的实现方式

基于数组的实现

使用数组存储元素，用一个变量记录栈顶位置。

C++ 实现

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

template <typename T>
class ArrayStack {
private:
    T* data;           // 数组指针
    int capacity;      // 容量
    int topIndex;      // 栈顶索引

public:
    // 构造函数
    ArrayStack(int cap = 10) : capacity(cap), topIndex(-1) {
        data = new T[capacity];
    }

    // 析构函数
    ~ArrayStack() {
        delete[] data;
    }

    // 入栈
    void push(const T& value) {
        if (isFull()) {
            // 扩容：容量翻倍
            resize(capacity * 2);
        }
        data[++topIndex] = value;
    }

    // 出栈
    T pop() {
        if (isEmpty()) {
            throw runtime_error("栈为空，无法出栈");
        }
        return data[topIndex--];
    }

    // 查看栈顶元素
    T top() const {
        if (isEmpty()) {
            throw runtime_error("栈为空");
        }
        return data[topIndex];
    }

    // 判断是否为空
    bool isEmpty() const {
        return topIndex == -1;
    }

    // 判断是否已满
    bool isFull() const {
        return topIndex == capacity - 1;
    }

    // 获取大小
    int size() const {
        return topIndex + 1;
    }

    // 打印栈内容
    void print() const {
        cout << "Stack (top -> bottom): ";
        for (int i = topIndex; i >= 0; i--) {
            cout << data[i] << " ";
        }
        cout << endl;
    }

private:
    // 扩容
    void resize(int newCapacity) {
        T* newData = new T[newCapacity];
        for (int i = 0; i <= topIndex; i++) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }
};

int main() {
    cout << "=== 测试int类型栈 ===" << endl;
    ArrayStack<int> intStack;  // 默认容量10

    // 测试判空
    cout << "初始栈是否为空：" << (intStack.isEmpty() ? "是" : "否") << endl;

    // 测试入栈（5个元素）
    intStack.push(10);
    intStack.push(20);
    intStack.push(30);
    intStack.push(40);
    intStack.push(50);
    cout << "入栈5个元素后：";
    intStack.print();
    cout << "当前栈大小：" << intStack.size() << endl;
    cout << "栈是否已满：" << (intStack.isFull() ? "是" : "否") << endl;

    // 测试查看栈顶
    cout << "当前栈顶元素：" << intStack.top() << endl;

    // 测试出栈
    int popVal = intStack.pop();
    cout << "出栈元素：" << popVal << endl;
    cout << "出栈后：";
    intStack.print();
    cout << "当前栈大小：" << intStack.size() << endl;

    // 测试扩容（继续入栈，触发扩容）
    cout << "\n--- 测试扩容功能 ---" << endl;
    // 现有4个元素，再入7个（共11个，超过默认容量10）
    intStack.push(60);
    intStack.push(70);
    intStack.push(80);
    intStack.push(90);
    intStack.push(100);
    intStack.push(110);
    intStack.push(120);
    cout << "扩容后栈内容：";
    intStack.print();
    cout << "当前栈容量：" << intStack.size() << endl;  // 11个元素
    cout << "栈是否已满：" << (intStack.isFull() ? "是" : "否") << endl;  // 新容量20，未满

    return 0;
}

下面来说一下使用栈来构建栈的优缺点

优点：

缓存友好
实现简单

缺点：

需要预先分配空间
扩容时需要复制数据（O(n)）
空间可能浪费

下面我们继续来说下，如何使用链表来实现栈

基于链表的实现

原理

使用链表存储元素，栈顶指向链表头部，插入新元素使用头插法

执行 TOP 时，我们直接返回 dummy->next 就可以了

C++ 实现

#include <iostream>
#include <stdexcept>
#include <string>  // 用于测试string类型栈
using namespace std;

template <typename T>
class LinkedStack {
private:
    // 节点结构
    struct Node {
        T data;
        Node* next;
        Node(const T& value) : data(value), next(nullptr) {}
    };

    Node* topNode;    // 栈顶指针
    int count;        // 元素个数

public:
    // 构造函数
    LinkedStack() : topNode(nullptr), count(0) {}

    // 析构函数
    ~LinkedStack() {
        while (!isEmpty()) {
            pop();
        }
    }

    // 入栈
    void push(const T& value) {
        Node* newNode = new Node(value);
        newNode->next = topNode;
        topNode = newNode;
        count++;
    }

    // 出栈
    T pop() {
        if (isEmpty()) {
            throw runtime_error("栈为空，无法出栈");
        }
        Node* temp = topNode;
        T value = temp->data;
        topNode = topNode->next;
        delete temp;
        count--;
        return value;
    }

    // 查看栈顶元素
    T top() const {
        if (isEmpty()) {
            throw runtime_error("栈为空，无法查看栈顶");
        }
        return topNode->data;
    }

    // 判断是否为空
    bool isEmpty() const {
        return topNode == nullptr;
    }

    // 获取大小
    int size() const {
        return count;
    }

    // 打印栈内容
    void print() const {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return;
        }
        cout << "Stack (top -> bottom): ";
        Node* current = topNode;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};

// main函数：全面测试LinkedStack的功能
int main() {
    LinkedStack<int> intStack;

    // 测试判空
    cout << "初始栈是否为空：" << (intStack.isEmpty() ? "是" : "否") << endl;
    cout << "初始栈大小：" << intStack.size() << endl;
    intStack.print();  // 测试空栈打印

    // 测试入栈（多个元素）
    cout << "\n--- 执行入栈操作 ---" << endl;
    intStack.push(100);
    intStack.push(200);
    intStack.push(300);
    intStack.push(400);
    cout << "入栈4个元素（100、200、300、400）后：";
    intStack.print();
    cout << "当前栈大小：" << intStack.size() << endl;
    cout << "栈顶元素：" << intStack.top() << endl;

    // 测试出栈（单个元素）
    cout << "\n--- 执行出栈操作 ---" << endl;
    int popVal1 = intStack.pop();
    cout << "出栈元素：" << popVal1 << endl;
    cout << "出栈后栈内容：";
    intStack.print();
    cout << "当前栈大小：" << intStack.size() << endl;
    cout << "栈顶元素：" << intStack.top() << endl;

    // 测试连续出栈（直到空栈前）
    cout << "\n--- 连续出栈2个元素 ---" << endl;
    int popVal2 = intStack.pop();
    int popVal3 = intStack.pop();
    cout << "连续出栈元素：" << popVal2 << "、" << popVal3 << endl;
    cout << "连续出栈后：";
    intStack.print();
    cout << "当前栈大小：" << intStack.size() << endl;

    return 0;
}

优缺点

优点：

动态大小，无需扩容
空间利用率高
插入删除不需要移动数据

缺点：

额外的指针开销
缓存局部性差
内存碎片

通过上面的内容，基本就完全掌握了栈的各项要素，下面我们来看一下 STL 的 stack 吧

使用 STL 的 stack

C++ 标准库提供了现成的栈实现。

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

int main() {
    stack<int> s;

    // 入栈
    s.push(10);
    s.push(20);
    s.push(30);

    // 查看栈顶
    cout << "栈顶元素: " << s.top() << endl;  // 30

    // 出栈
    s.pop();
    cout << "出栈后栈顶: " << s.top() << endl;  // 20

    // 大小
    cout << "栈大小: " << s.size() << endl;  // 2

    // 判断是否为空
    cout << "是否为空: " << (s.empty() ? "是" : "否") << endl;

    return 0;
}

实现方式对比

特性	数组实现	链表实现	STL stack
时间复杂度（平均）	O(1)	O(1)	O(1)
扩容开销	有	无	有
空间开销	低	高（指针）	低
缓存性能	好	差	好
实现难度	中	中	易（直接使用）

平常不建议大家造轮子，有可以用的直接拿来用就好，把时间用在刀刃上，下面继续说一下，栈的应用场景

栈的应用场景

表达式求值

栈在现实中应用场景很多，大家在刷题时就可以注意到，很多题目都可以用栈来解决的。下面我们来说一个比较常用的情景，数字表达式的求值。

不知道大家是否还记得那句口令，先乘除，后加减，从左算到右，有括号的话就先算括号里面的。

这是我们做小学数学所用到的。四则运算中括号也是其中的一部分，先乘除后加减使运算变的复杂，加上括号后甚之，那么我们有什么办法可以让其变的更好处理呢？

波兰数学家Jan Łukasiewicz想到了一种不需要括号的后缀表达式，我们也将它称之为逆波兰表示。

不用数学家名字命名的原因有些尴尬，居然是因为他的名字太复杂了，所以用了国籍来表示而不是姓名。所以各位小伙伴以后给孩子起名字的时候不要太复杂啊。

扬·武卡谢维奇（波兰语open in new window：Jan Łukasiewicz，1878 年 12 月 21 日**乌克兰open in new window利沃夫 - 1956 年 2 月 13 日爱尔兰都柏林），波兰open in new window数学家，主要致力于数理逻辑open in new window**的研究。著名的波兰表示法逆波兰表示法就是他的研究成果。

中缀表达式转为后缀表达式

我们通过一个例子，来说明如何将中缀表达式转为后缀表达式。

例

中缀:9 + ( 3 - 1 ) * 3 + 10 / 2

后缀:9 3 1 - 3 * + 10 2 / +

规则

1.从左到右遍历中缀表达式的每个数字和符号，若是数字就输出（直接成为后缀表达式的一部分，不进入栈）

2.若是符号则判断其与栈顶符号的优先级，是右括号或低于栈顶元素，则栈顶元素依次出栈并输出，等出栈完毕，当前元素入栈。

3.遵循以上两条直到输出后缀表达式为止。

老样子大家直接看动图吧简单粗暴，清晰易懂

后缀表达式计算结果

中缀:9 + ( 3 - 1 ) * 3 + 10 / 2=20

后缀:9 3 1 - 3 * + 10 2 / +

后缀表达式的值也为 20，那么我们来了解一下计算机是如何将后缀表达式计算为 20 的。

规则：

1.从左到右遍历表达式的每个数字和符号，如果是数字就进栈

2.如果是符号就将栈顶的两个数字出栈，进行运算，并将结果入栈，一直到获得最终结果。

下面大家继续看动图吧。

本章内容就到这里了，希望能够对大家有一些帮助

03、栈

# 生活中的栈

# 栈的定义

# 栈的基本操作

# 核心操作

# 操作示例

# 栈的实现方式

# 基于数组的实现

# C++ 实现

# 下面来说一下使用栈来构建栈的优缺点

# 基于链表的实现

# 原理

# C++ 实现

# 优缺点

# 使用 STL 的 stack

# 实现方式对比

# 栈的应用场景

# 表达式求值

# 中缀表达式转为后缀表达式

# 后缀表达式计算结果

生活中的栈

栈的定义

栈的基本操作

核心操作

操作示例

栈的实现方式

基于数组的实现

C++ 实现

下面来说一下使用栈来构建栈的优缺点

基于链表的实现

原理

C++ 实现

优缺点

使用 STL 的 stack

实现方式对比

栈的应用场景

表达式求值

中缀表达式转为后缀表达式

后缀表达式计算结果