C++ 实现堆栈深入讲解

C++ 堆栈基础概念

在计算机科学中，堆栈（Stack）是一种重要的数据结构，它遵循后进先出（Last In First Out, LIFO）的原则。想象一下一叠盘子，最后放上的盘子会最先被拿走，这就是堆栈的工作方式。在 C++ 编程中，理解和掌握堆栈的实现对于开发高效、健壮的程序至关重要。

堆栈的操作

1. 入栈（Push）：将一个元素添加到堆栈的顶部。这就像是把一个盘子放在一叠盘子的最上面。
2. 出栈（Pop）：从堆栈顶部移除一个元素。类似于拿走最上面的盘子。
3. 查看栈顶元素（Top）：获取堆栈顶部的元素，但不将其移除。好比看一眼最上面的盘子，但不拿走它。
4. 判断堆栈是否为空（IsEmpty）：检查堆栈中是否有元素。若堆栈为空，就像一叠盘子都被拿走了，没有盘子了。

C++ 实现堆栈的方式

基于数组的堆栈实现

1. 原理：使用数组来存储堆栈中的元素。数组有连续的内存空间，适合简单直接地实现堆栈。我们通过一个变量来记录堆栈的当前顶部位置。
2. 代码示例：

#include <iostream>
#include <limits>

class StackUsingArray {
private:
    int* stackArray;
    int topIndex;
    int capacity;

public:
    StackUsingArray(int cap) : capacity(cap), topIndex(-1) {
        stackArray = new int[capacity];
    }

    ~StackUsingArray() {
        delete[] stackArray;
    }

    void push(int value) {
        if (isFull()) {
            std::cerr << "Stack overflow" << std::endl;
            return;
        }
        stackArray[++topIndex] = value;
    }

    int pop() {
        if (isEmpty()) {
            std::cerr << "Stack underflow" << std::endl;
            return std::numeric_limits<int>::min();
        }
        return stackArray[topIndex--];
    }

    int top() {
        if (isEmpty()) {
            std::cerr << "Stack is empty" << std::endl;
            return std::numeric_limits<int>::min();
        }
        return stackArray[topIndex];
    }

    bool isEmpty() {
        return topIndex == -1;
    }

    bool isFull() {
        return topIndex == capacity - 1;
    }
};

int main() {
    StackUsingArray stack(5);
    stack.push(10);
    stack.push(20);
    std::cout << "Top element: " << stack.top() << std::endl;
    std::cout << "Popped element: " << stack.pop() << std::endl;
    std::cout << "Is stack empty? " << (stack.isEmpty()? "Yes" : "No") << std::endl;
    return 0;
}

3. 优缺点：
   • 优点：实现简单，访问速度快，因为数组元素在内存中是连续存储的，可以通过索引快速定位。
   • 缺点：大小固定，一旦初始化就不能动态改变容量。如果堆栈中的元素数量超过初始容量，就会发生堆栈溢出错误。

基于链表的堆栈实现

1. 原理：利用链表的节点结构来构建堆栈。每个节点包含数据和指向下一个节点的指针。堆栈的顶部就是链表的头节点。
2. 代码示例：

#include <iostream>
#include <limits>

struct StackNode {
    int data;
    StackNode* next;
    StackNode(int value) : data(value), next(nullptr) {}
};

class StackUsingLinkedList {
private:
    StackNode* topNode;

public:
    StackUsingLinkedList() : topNode(nullptr) {}

    ~StackUsingLinkedList() {
        while (!isEmpty()) {
            pop();
        }
    }

    void push(int value) {
        StackNode* newNode = new StackNode(value);
        newNode->next = topNode;
        topNode = newNode;
    }

    int pop() {
        if (isEmpty()) {
            std::cerr << "Stack underflow" << std::endl;
            return std::numeric_limits<int>::min();
        }
        int poppedValue = topNode->data;
        StackNode* temp = topNode;
        topNode = topNode->next;
        delete temp;
        return poppedValue;
    }

    int top() {
        if (isEmpty()) {
            std::cerr << "Stack is empty" << std::endl;
            return std::numeric_limits<int>::min();
        }
        return topNode->data;
    }

    bool isEmpty() {
        return topNode == nullptr;
    }
};

int main() {
    StackUsingLinkedList stack;
    stack.push(10);
    stack.push(20);
    std::cout << "Top element: " << stack.top() << std::endl;
    std::cout << "Popped element: " << stack.pop() << std::endl;
    std::cout << "Is stack empty? " << (stack.isEmpty()? "Yes" : "No") << std::endl;
    return 0;
}

3. 优缺点：
   • 优点：动态性强，可以根据需要随时添加或移除节点，不会出现固定大小的限制，避免了堆栈溢出问题。
   • 缺点：由于每个节点都需要额外的指针来指向下一个节点，所以占用的内存空间相对较大。而且链表的节点在内存中不是连续存储的，访问速度相对数组较慢。

标准库中的堆栈

std::stack 简介

C++ 标准库提供了 std::stack 容器适配器，它基于其他标准容器（如 std::deque、std::list 或 std::vector）来实现堆栈功能。这使得我们可以在不自己实现底层数据结构的情况下，方便地使用堆栈。

1. 头文件：使用 std::stack 需包含 <stack> 头文件。
2. 声明方式：

#include <stack>
#include <vector>
#include <list>
// 使用 std::vector 作为底层容器
std::stack<int, std::vector<int>> stackWithVector;
// 使用 std::list 作为底层容器
std::stack<int, std::list<int>> stackWithList;
// 默认使用 std::deque 作为底层容器
std::stack<int> defaultStack;

std::stack 的常用操作

1. push()：将元素压入堆栈顶部。

std::stack<int> myStack;
myStack.push(10);

2. pop()：移除堆栈顶部的元素。

myStack.pop();

3. top()：获取堆栈顶部的元素。

int topElement = myStack.top();

4. empty()：判断堆栈是否为空。

bool isEmpty = myStack.empty();

5. size()：获取堆栈中元素的数量。

size_t stackSize = myStack.size();

std::stack 的底层实现分析

1. 默认底层容器：std::stack 默认使用 std::deque 作为底层容器。std::deque（双端队列）具有在两端高效插入和删除元素的特点，这正好适合堆栈的操作。它在内存管理上采用分段连续的存储方式，既避免了数组固定大小的缺点，又能在一定程度上保持较好的访问性能。
2. 选择其他底层容器：我们也可以选择 std::vector 或 std::list 作为底层容器。如果选择 std::vector，由于其连续的内存存储结构，在访问元素时效率较高，但在插入和删除元素（特别是在头部）时可能需要移动大量元素，性能相对较差。而 std::list 是链表结构，插入和删除元素非常高效，但随机访问性能较差。

堆栈在实际编程中的应用

表达式求值

1. 中缀表达式转换为后缀表达式（逆波兰表达式）：中缀表达式是我们日常书写数学表达式的方式，如 3 + 4 * 2。而后缀表达式是将运算符紧跟在操作数之后，如 3 4 2 * +。在计算机中，后缀表达式更易于求值。可以使用堆栈来实现中缀到后缀的转换。
   • 算法思路：扫描中缀表达式，操作数直接输出，运算符根据其优先级和堆栈状态处理。优先级高的运算符先入栈，优先级低的运算符等待优先级高的运算符出栈后再入栈。括号有特殊处理，左括号直接入栈，右括号使栈顶元素弹出直到遇到左括号。
   • 代码示例：

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <cctype>

int precedence(char op) {
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return 0;
}

std::string infixToPostfix(const std::string& infix) {
    std::stack<char> operatorStack;
    std::ostringstream postfix;
    for (char ch : infix) {
        if (std::isspace(ch)) continue;
        if (std::isdigit(ch)) {
            postfix << ch;
        } else if (ch == '(') {
            operatorStack.push(ch);
        } else if (ch == ')') {
            while (!operatorStack.empty() && operatorStack.top() != '(') {
                postfix << operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.pop(); // 移除左括号
        } else { // 运算符
            while (!operatorStack.empty() && precedence(operatorStack.top()) >= precedence(ch)) {
                postfix << operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.push(ch);
        }
    }
    while (!operatorStack.empty()) {
        postfix << operatorStack.top();
        operatorStack.pop();
    }
    return postfix.str();
}

int main() {
    std::string infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
    std::string postfix = infixToPostfix(infix);
    std::cout << "Postfix expression: " << postfix << std::endl;
    return 0;
}

2. 后缀表达式求值：使用堆栈可以方便地对后缀表达式进行求值。扫描后缀表达式，操作数入栈，遇到运算符时，从栈中弹出相应数量的操作数进行运算，并将结果入栈。
   • 算法思路：初始化一个空堆栈，遍历后缀表达式。如果是操作数，将其转换为数值并入栈。如果是运算符，从栈中弹出两个操作数，进行运算，将结果入栈。遍历结束后，栈顶元素就是表达式的结果。
   • 代码示例：

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <cctype>
#include <cmath>

int applyOperator(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        case '^': return std::pow(a, b);
        default: return 0;
    }
}

int evaluatePostfix(const std::string& postfix) {
    std::stack<int> operandStack;
    for (char ch : postfix) {
        if (std::isdigit(ch)) {
            operandStack.push(ch - '0');
        } else {
            int b = operandStack.top();
            operandStack.pop();
            int a = operandStack.top();
            operandStack.pop();
            int result = applyOperator(a, b, ch);
            operandStack.push(result);
        }
    }
    return operandStack.top();
}

int main() {
    std::string postfix = "342*+15-23^^/";
    int result = evaluatePostfix(postfix);
    std::cout << "Evaluated result: " << result << std::endl;
    return 0;
}

函数调用栈

1. 原理：在 C++ 程序执行过程中，每当调用一个函数时，系统会在内存的堆栈区域为该函数创建一个栈帧（Stack Frame）。栈帧包含了函数的参数、局部变量以及函数返回地址等信息。当函数执行完毕，其栈帧会从堆栈中弹出。这种机制保证了函数调用的正确顺序和局部变量的正确生命周期管理。
2. 示例分析：

void functionB() {
    int localVarB = 10;
    // 函数 B 的代码逻辑
}

void functionA() {
    int localVarA = 20;
    functionB();
    // 函数 A 的代码逻辑
}

int main() {
    functionA();
    return 0;
}

在上述代码中，当 main 函数调用 functionA 时，系统为 functionA 创建一个栈帧，包含 localVarA 等信息。functionA 调用 functionB 时，又为 functionB 创建一个栈帧，包含 localVarB。functionB 执行完毕，其栈帧弹出。接着 functionA 执行完毕，其栈帧弹出。最后 main 函数执行完毕，程序结束。理解函数调用栈对于调试程序、分析递归函数等都非常重要。

深度优先搜索（DFS）算法

1. 原理：深度优先搜索是一种用于遍历或搜索图或树结构的算法。它从起始节点开始，尽可能深地探索每个分支，直到无法继续或达到目标节点。在实现 DFS 时，可以使用堆栈来模拟递归调用的过程。将起始节点入栈，然后循环从栈中弹出节点并访问，将其未访问的邻接节点入栈，直到堆栈为空。
2. 代码示例：以一个简单的无向图为例，使用邻接表表示图结构。

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

class Graph {
private:
    int numVertices;
    std::vector<std::vector<int>> adjList;

public:
    Graph(int vertices) : numVertices(vertices), adjList(vertices) {}

    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        adjList[dest].push_back(src);
    }

    void DFS(int start) {
        std::vector<bool> visited(numVertices, false);
        std::stack<int> stack;
        stack.push(start);
        visited[start] = true;

        while (!stack.empty()) {
            int current = stack.top();
            stack.pop();
            std::cout << current << " ";
            for (int neighbor : adjList[current]) {
                if (!visited[neighbor]) {
                    stack.push(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
};

int main() {
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(2, 0);
    graph.addEdge(2, 3);
    graph.addEdge(3, 3);
    graph.addEdge(4, 4);

    std::cout << "DFS starting from vertex 0: ";
    graph.DFS(0);
    std::cout << std::endl;
    return 0;
}

在上述代码中，通过堆栈实现了深度优先搜索，按照深度优先的顺序遍历图中的节点。

堆栈实现的优化与注意事项

内存管理优化

1. 基于数组的堆栈：如果使用动态分配的数组（如 new int[capacity]），在堆栈析构时要确保正确释放内存，避免内存泄漏。可以考虑使用智能指针（如 std::unique_ptr<int[]>）来简化内存管理。

#include <iostream>
#include <memory>
#include <limits>

class StackUsingArray {
private:
    std::unique_ptr<int[]> stackArray;
    int topIndex;
    int capacity;

public:
    StackUsingArray(int cap) : capacity(cap), topIndex(-1) {
        stackArray.reset(new int[capacity]);
    }

    // 析构函数由 std::unique_ptr 自动处理内存释放

    void push(int value) {
        if (isFull()) {
            std::cerr << "Stack overflow" << std::endl;
            return;
        }
        stackArray[++topIndex] = value;
    }

    int pop() {
        if (isEmpty()) {
            std::cerr << "Stack underflow" << std::endl;
            return std::numeric_limits<int>::min();
        }
        return stackArray[topIndex--];
    }

    int top() {
        if (isEmpty()) {
            std::cerr << "Stack is empty" << std::endl;
            return std::numeric_limits<int>::min();
        }
        return stackArray[topIndex];
    }

    bool isEmpty() {
        return topIndex == -1;
    }

    bool isFull() {
        return topIndex == capacity - 1;
    }
};

2. 基于链表的堆栈：在链表节点的插入和删除操作中，要确保正确分配和释放内存。同样可以使用智能指针（如 std::unique_ptr<StackNode>）来管理链表节点。

#include <iostream>
#include <memory>
#include <limits>

struct StackNode {
    int data;
    std::unique_ptr<StackNode> next;
    StackNode(int value) : data(value), next(nullptr) {}
};

class StackUsingLinkedList {
private:
    std::unique_ptr<StackNode> topNode;

public:
    StackUsingLinkedList() : topNode(nullptr) {}

    // 析构函数由 std::unique_ptr 自动处理节点内存释放

    void push(int value) {
        std::unique_ptr<StackNode> newNode(new StackNode(value));
        newNode->next = std::move(topNode);
        topNode = std::move(newNode);
    }

    int pop() {
        if (isEmpty()) {
            std::cerr << "Stack underflow" << std::endl;
            return std::numeric_limits<int>::min();
        }
        int poppedValue = topNode->data;
        topNode = std::move(topNode->next);
        return poppedValue;
    }

    int top() {
        if (isEmpty()) {
            std::cerr << "Stack is empty" << std::endl;
            return std::numeric_limits<int>::min();
        }
        return topNode->data;
    }

    bool isEmpty() {
        return topNode == nullptr;
    }
};

错误处理

1. 堆栈溢出：基于数组的堆栈要检查容量，当堆栈满时，不能再进行 push 操作。在 push 方法中可以添加错误处理，如打印错误信息并返回。

void push(int value) {
    if (isFull()) {
        std::cerr << "Stack overflow" << std::endl;
        return;
    }
    stackArray[++topIndex] = value;
}

2. 堆栈下溢：在 pop 和 top 操作中，要检查堆栈是否为空。如果为空，不能进行相应操作，可以返回一个特殊值（如 std::numeric_limits<int>::min()）并打印错误信息。

int pop() {
    if (isEmpty()) {
        std::cerr << "Stack underflow" << std::endl;
        return std::numeric_limits<int>::min();
    }
    return stackArray[topIndex--];
}

int top() {
    if (isEmpty()) {
        std::cerr << "Stack is empty" << std::endl;
        return std::numeric_limits<int>::min();
    }
    return stackArray[topIndex];
}

性能考虑

1. 基于数组的堆栈：访问速度快，但如果需要频繁改变堆栈大小，重新分配内存会带来性能开销。在初始化数组时，可以根据预估的最大元素数量来设置合适的容量，减少内存重新分配的次数。
2. 基于链表的堆栈：插入和删除操作高效，但由于内存不连续，随机访问性能差。如果应用场景主要是频繁的插入和删除，链表实现更合适；如果需要频繁随机访问元素，数组实现可能更好。在选择 std::stack 的底层容器时，也要根据实际应用的性能需求来决定。例如，如果需要快速访问元素且插入删除操作不频繁，选择 std::vector 作为底层容器；如果插入删除操作频繁，选择 std::list 或默认的 std::deque 可能更合适。

通过深入理解 C++ 中堆栈的实现方式、应用场景以及优化和注意事项，开发者可以在实际编程中更好地利用堆栈这一强大的数据结构，编写出高效、健壮的程序。无论是简单的表达式求值，还是复杂的图算法实现，堆栈都能发挥重要作用。