数据结构：栈（Stack）

目录

从一个基本问题开始 

定义栈的基本操作

如何从零开始做一个栈？

第一步：回归最本质的需求

第二步：选择最基础的“容器”

路线一：基于“连续内存”（数组）的推导

路线二：基于“链条”（链表）的推导

复杂度分析

从一个基本问题开始 

想象一下，你正在编写一个非常简单的文本编辑器。你希望加入一个“撤销”（Undo）功能。用户每输入一个字，我们就记录下来。当用户点击“撤销”时，程序需要删除最近输入的那一个字。

• 用户输入 "A"，我们记录 "A"。

• 用户接着输入 "B"，我们记录 "B"。现在的文本是 "AB"。

• 用户又输入 "C"，我们记录 "C"。现在的文本是 "ABC"。

现在，用户想要撤销。他最想撤销的，自然是最后输入的 "C"。撤销后，文本变回 "AB"。如果他再按一次撤销，就应该撤销 "B"，文本变回 "A"。

我们发现了什么规律？最晚被记录的操作，需要最早被撤销。

这个规律，我们可以用一句话来概括：后进先出 (Last-In, First-Out)。

为了在程序里实现这个逻辑，我们需要一种专门存放数据的方式，它必须严格遵守“后进先出”的原则。我们不能随便从中间取数据，也不能从最开始的地方取数据，只能从“最后加入数据”的那个口子取。

这种为了解决“后进先出”问题而设计的数据存储结构，我们就给它起个名字，叫做 “栈” (Stack)。

定义栈的基本操作

现在我们知道了“为什么”需要栈。接下来我们定义一下，一个合格的“栈”应该具备哪些基本能力（这在学术上称为抽象数据类型 ADT - Abstract Data Type）。

数据结构：数组抽象数据类型（Array ADT）_数据结构 adt-CSDN博客

• 入栈 (Push): 向栈的顶部添加一个新元素。就像我们把一本新书放在一摞书的最上面。

• 出栈 (Pop): 从栈的顶部移除一个元素，并可以得到这个元素的值。就像我们从一摞书的最上面拿走一本书。

• 查看栈顶 (Peek / Top): 只是看一下栈顶的元素是什么，但不把它拿走。

• 判空 (isEmpty): 判断栈里是不是一个元素都没有了。

• 获取大小 (Size): 获取栈里当前有多少个元素。

我们所有的操作都只围绕“栈顶”进行，完美地遵守了“后进先出”的原则。

如何从零开始做一个栈？

第一步：回归最本质的需求

我们先忘掉“数据结构”这个词。想象一下，我们遇到了一个非常具体的问题：需要处理一些数据，这些数据有一个严格的顺序要求：最后进来的数据，必须第一个被处理。

就像我们把一摞盘子叠在一起：

1. 放第一个盘子在桌上。

2. 放第二个盘子在第一个上面。

3. 放第三个盘子在第二个上面。

当我们要用盘子时，我们肯定会从最上面，也就是第三个盘子开始拿。拿完第三个，才能拿第二个。这就是“后进先出”（Last-In, First-Out, LIFO）的原则。

我们的目标，就是要在程序里，用最基础的语法（变量、内存、指针）来模拟这个过程。

第二步：选择最基础的“容器”

要在程序里存放一堆数据，最基本的方式是什么？无非两种：

1. 找一块连续的内存空间，挨个放进去。 这在 C/C++ 里对应的就是 数组。

2. 数据可以随便放，但用一根“链条”把它们按顺序串起来。 这对应的就是 链表。

这两种方式，就是我们从零创造栈的两个不同技术路线。我们逐一推导。

路线一：基于“连续内存”（数组）的推导

推导过程：

1. 选定容器：我们决定用数组来存放数据。先声明一个数组，比如 int data[N];，这里 N 是我们预估的最大容量。我们还需要知道这个栈最多能装多少元素，所以需要一个变量 capacity 来记录数组的总大小。

2. 核心问题：如何表示“顶”？ 数组本身是静态的，它不知道哪个是“最后”放进来的元素。我们需要一个“标记”来时刻指向这个“栈顶”位置。最简单的标记就是用一个整数变量来记录数组的下标。我们叫它 top。

3. 定义“空”的状态：当一个盘子都没有的时候，我们的“顶”在哪里？这是一个需要我们自己定义规则的时刻。最直观的约定是，当栈为空时，top 指向一个无效的、不存在的下标。对于从 0 开始的数组，-1 就是一个绝佳的选择。所以，我们规定：top = -1 代表栈是空的。

4. 推导“放盘子”（入栈 / Push）操作：

   • 要放入一个新盘子（元素 e），应该放在哪里？显然是当前“顶”的上面一个位置。

   • 操作顺序是：先把 top 的值加 1，让它指向新的空位。

   • 然后，把元素 e 放到 data[top] 这个位置。

   • 伪代码就是：top = top + 1; 然后 data[top] = e;

5. 推导“拿盘子”（出栈 / Pop）操作：

   • 要拿走最上面的盘子，我们应该从哪里拿？当然是 top 正指向的位置。

   • 操作顺序是：先把 data[top] 的值取出来（如果需要返回这个值的话）。

   • 然后，把 top 的值减 1，让它指向下面一个元素，这个元素就成为了新的“顶”。

   • 伪代码就是：e = data[top]; 然后 top = top - 1;

6. 增加健壮性：

   • 在“放盘子”前，要检查一下盘子摞得是不是太高了，超出了我们预留的空间。也就是判断 top 是不是已经等于 N-1（数组最后一个下标）了。如果是，就不能再放了，这就是“栈满”。

   • 在“拿盘子”前，要检查一下是不是已经没有盘子可拿了。也就是判断 top 是不是等于 -1。如果是，就不能再拿了，这就是“栈空”。

7. 封装成一个“东西”：我们发现，一个完整的“栈”需要数组 data、栈顶指针 top 和容量 N 这三样东西紧密配合。为了方便管理和使用，我们应该把它们打包在一起。在 C 语言里，我们用 struct；在 C++ 里，我们用 class 或 struct。

#include <iostream>

// 我们先定义一个常量作为栈的默认大小
const int STACK_CAPACITY = 100;

class MyStack {
private: // 这些是栈内部的实现细节，外界不应直接访问
    int* data;      // 指向我们申请的连续内存（数组）
    int top_index;  // 我们的“栈顶”标记，使用 top_index 代替 top 避免与C++关键字冲突
    int capacity;   // 这个栈最多能存多少元素

public:
    // 构造函数：当我们创建一个栈对象时，需要在这里完成初始化
    MyStack(int size = STACK_CAPACITY) {
        std::cout << "第一步：申请一块连续内存作为容器。" << std::endl;
        capacity = size;
        data = new int[capacity]; // 动态申请内存
        
        std::cout << "第二步：定义'空'的状态。" << std::endl;
        top_index = -1; // -1 代表栈是空的
        std::cout << "一个新栈创建了，容量为 " << capacity << "，当前为空。" << std::endl;
    }

    // 析构函数：当栈对象生命周期结束时，释放内存
    ~MyStack() {
        delete[] data;
        std::cout << "栈被销毁，内存已释放。" << std::endl;
    }

    // 入栈操作 (Push)
    void push(int value) {
        std::cout << "推导'入栈'：先检查是否已满。" << std::endl;
        if (top_index >= capacity - 1) {
            std::cout << "错误：栈已满！无法放入 " << value << std::endl;
            return;
        }
        
        std::cout << "推导'入栈'：top 指针上移，再放入数据。" << std::endl;
        top_index++;
        data[top_index] = value;
        std::cout << value << " 已入栈，现在栈顶是 " << data[top_index] << std::endl;
    }

    // 出栈操作 (Pop)
    void pop() {
        std::cout << "推导'出栈'：先检查是否为空。" << std::endl;
        if (top_index == -1) {
            std::cout << "错误：栈已空！无法出栈。" << std::endl;
            return;
        }
        
        std::cout << "推导'出栈'：取出数据，top 指针下移。" << std::endl;
        std::cout << data[top_index] << " 已出栈。" << std::endl;
        top_index--;
    }

    // 查看栈顶元素 (Top/Peek)
    int top() {
        if (top_index == -1) {
            std::cout << "错误：栈已空！" << std::endl;
            return -1; // 返回一个错误值
        }
        return data[top_index];
    }
    
    // 判断是否为空
    bool empty() {
        return top_index == -1;
    }
};

c语言风格：

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

#define MAX_SIZE 100 // 定义栈的最大容量

// 定义顺序栈的结构体
typedef struct {
    int* data;      // 指向存储数据的数组
    int top;        // 指向栈顶的索引
    int capacity;   // 栈的容量
} SequentialStack;

路线二：基于“链条”（链表）的推导

推导过程：

1. 选定容器：这次我们不用连续空间。我们定义一个“节点 (Node)”的结构，每个节点能存放一个数据，同时包含一个“钩子”（指针 next）用来链接到下一个节点。

2. 核心问题：哪里是“顶”？ 对于链表，最方便进行插入和删除操作的位置是链表的头部。所以，我们很自然地选择把链表的头节点当作“栈顶”。我们只需要一个指针，叫 top，让它永远指向链表的头节点。

3. 定义“空”的状态：如果链表里一个节点都没有，那 top 指针应该指向哪里？它无处可指，所以我们规定：top = NULL (或 nullptr) 代表栈是空的。

4. 推导“放盘子”（入栈 / Push）操作：

   • 这相当于在链表的头部插入一个新节点。

   • 首先，我们需要创建一个新的节点 newNode，并把数据 e 放进去。

   • 然后，把这个 newNode 的“钩子” (next 指针) 挂到当前的“顶” (top 指针指向的节点)上。

   • 最后，移动 top 指针，让它指向这个 newNode，因为 newNode 已经成为了新的栈顶。

   • 伪代码：newNode->next = top; 然后 top = newNode;

5. 推导“拿盘子”（出栈 / Pop）操作：

   • 这相当于删除链表的头节点。

   • 首先，我们需要一个临时指针 temp 先记住当前的栈顶 top，防止它丢失。

   • 然后，让 top 指针移动到下一个节点，也就是 top = top->next;。此时 top 已经指向了新的栈顶。

   • 最后，我们可以安全地释放掉 temp 指向的那个旧的栈顶节点的内存。

   • 伪代码：temp = top; top = top->next; free(temp);

6. 健壮性：

   • 链式结构理论上没有“满”的状态，只要机器内存足够，就可以一直申请新节点。

   • 在“拿盘子”前，同样需要检查是否为空，即判断 top 是否为 NULL。

7. 封装：我们把 Node 的定义和 top 指针的管理封装在一个类里。

#include <iostream>

// 先推导出“节点”这个基本单元
struct Node {
    int data;       // 数据域
    Node* next;     // 指针域，指向下一个节点
};

class MyLinkedStack {
private:
    Node* top_ptr; // 只需要一个指向栈顶的指针

public:
    // 构造函数：初始化
    MyLinkedStack() {
        std::cout << "第一步：定义'空'的状态。" << std::endl;
        top_ptr = nullptr; // C++11 推荐使用 nullptr
        std::cout << "一个新链式栈创建了，当前为空。" << std::endl;
    }

    // 析构函数：释放所有节点内存
    ~MyLinkedStack() {
        while (!empty()) {
            pop(); // 不断出栈，pop 内部会释放节点
        }
        std::cout << "链式栈被销毁，所有节点内存已释放。" << std::endl;
    }

    // 入栈操作 (Push)
    void push(int value) {
        std::cout << "推导'入栈'：创建一个新节点。" << std::endl;
        Node* newNode = new Node();
        newNode->data = value;
        
        std::cout << "推导'入栈'：新节点指向旧栈顶，然后自己成为新栈顶。" << std::endl;
        newNode->next = top_ptr;
        top_ptr = newNode;
        
        std::cout << value << " 已入栈。" << std::endl;
    }

    // 出栈操作 (Pop)
    void pop() {
        std::cout << "推导'出栈'：先检查是否为空。" << std::endl;
        if (empty()) {
            std::cout << "错误：栈已空！无法出栈。" << std::endl;
            return;
        }
        
        std::cout << "推导'出栈'：保存旧栈顶，top 指针下移，释放旧栈顶内存。" << std::endl;
        Node* temp = top_ptr;
        top_ptr = top_ptr->next;
        
        std::cout << temp->data << " 已出栈。" << std::endl;
        delete temp; // 释放内存
    }

    // 查看栈顶元素 (Top/Peek)
    int top() {
        if (empty()) {
            std::cout << "错误：栈已空！" << std::endl;
            return -1; // 返回一个错误值
        }
        return top_ptr->data;
    }
    
    // 判断是否为空
    bool empty() {
        return top_ptr == nullptr;
    }
};

c语言风格：

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

// 定义链式栈的节点
typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

// 定义链式栈的结构体
// 其实只需要一个指向栈顶的指针就够了
typedef struct {
    StackNode* top; // 永远指向栈顶节点
} LinkedStack;

复杂度分析

无论用哪种方式实现，栈的核心操作（入栈、出栈、查看栈顶）都只涉及对“栈顶”这一个位置的修改。我们不需要遍历整个数据集合去找到插入或删除点。

因此，这些核心操作的时间复杂度都是常数级的。

• 入栈 (Push): O(1)

• 出栈 (Pop): O(1)

• 查看栈顶 (Peek): O(1)

这里的 O(1) 表示操作花费的时间是固定的，与栈里已经有多少元素无关。这使得栈成为一个效率非常高的数据结构。