C++实战：栈和队列在问题解决中的7大应用


# 摘要
本文深入探讨了C++中栈和队列数据结构的基本概念、应用、实现细节及其在问题解决中的重要性。文中详细介绍了栈和队列的基本操作、存储方法以及在算法中的应用实例，如括号匹配、函数调用栈、表达式求值、深度优先搜索（DFS）、广度优先搜索（BFS）以及任务调度等。同时，本文分析了双端队列、堆栈以及多层栈的高级数据结构应用和使用场景。最后，通过对C++实战案例的解析以及性能优化和实战技巧的讨论，本文旨在为开发者提供全面的栈和队列应用指南，提高编程效率和程序性能。

# 关键字
栈；队列；数据结构；算法应用；性能优化；C++标准库

参考资源链接：[C++第4版《数据结构与算法分析》高清PDF下载指南](https://wenku.csdn.net/doc/7mtwrxpgck?spm=1055.2635.3001.10343)
# 1. C++中栈和队列的基本概念

## 1.1 数据结构的基本理念

数据结构是组织和存储数据的方式，使得数据的处理变得高效。在诸多数据结构中，栈（Stack）和队列（Queue）是非常基础且重要的两种结构。它们都归属于线性数据结构，但操作数据的方式不同，栈是后进先出（LIFO）的结构，而队列是先进先出（FIFO）的结构。这两种数据结构在解决诸如函数调用、撤销操作、任务调度等问题时，提供了简洁有效的解决方案。

## 1.2 栈（Stack）的特性

栈是一种特殊的线性表，只能在表的一端进行插入和删除操作，这一端称为栈顶（Top），另一端则称为栈底（Bottom）。栈的基本操作包括：`push`（入栈）、`pop`（出栈）、`peek`（查看栈顶元素）和`isEmpty`（判断栈是否为空）。这些操作保证了栈的后进先出的特性，意味着最后入栈的元素将最先被出栈。

## 1.3 队列（Queue）的特性

与栈类似，队列也是线性表的一种，但其操作和元素的存取方式与栈完全不同。队列的操作主要发生在两端：一端用于入队（enqueue），称为队尾（Rear）；另一端用于出队（dequeue），称为队头（Front）。队列的基本操作包括：`enqueue`（入队）、`dequeue`（出队）、`front`（查看队头元素）和`isEmpty`（判断队列是否为空）。队列的先进先出的特性使得它非常适合处理需要按到达顺序处理的任务，例如打印队列和缓冲处理。

以上内容仅是对栈和队列在C++中的基本概念进行的简单介绍，后续章节我们将详细探讨它们在实际编程问题中的应用和优化策略。

# 2. 栈在问题解决中的应用

## 2.1 栈的基本操作和实现

### 2.1.1 栈的定义和主要操作

栈是一种遵循后进先出（LIFO, Last In First Out）原则的数据结构，支持两种操作：入栈（push）和出栈（pop）。这意味着最后入栈的元素会最先出栈。在计算机科学中，栈在许多算法中发挥着重要作用。

栈的实现可以是顺序的也可以是链式的。顺序栈是基于数组实现，而链式栈是基于链表实现。在顺序栈中，通常有一个指针（或索引）用来指示栈顶的位置。在链式栈中，链表的头部是栈顶，元素按照后进先出的顺序排列。

### 2.1.2 栈的顺序存储和链式存储

#### 顺序栈的实现

顺序栈通常使用一个数组来实现，数组的大小为栈的最大容量。数组的某个位置`top`表示栈顶位置（初始值通常为-1），每次入栈时，`top`递增，并在`top`位置存放新元素；每次出栈时，返回`top`位置的元素，并递减`top`。

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

class Stack {
private:
    vector<int> stackArray;
    int capacity;

public:
    Stack(int cap) : capacity(cap) {}

    bool isFull() {
        return stackArray.size() == capacity;
    }

    bool isEmpty() {
        return stackArray.size() == 0;
    }

    void push(int item) {
        if (isFull()) {
            cout << "Stack is Full" << endl;
        } else {
            stackArray.push_back(item);
        }
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack is Empty" << endl;
            return -1;
        } else {
            int top = stackArray.back();
            stackArray.pop_back();
            return top;
        }
    }
};

int main() {
    Stack stack(3);
    stack.push(1);
    stack.push(2);
    stack.push(3);

    cout << "Popped: " << stack.pop() << endl;
    cout << "Popped: " << stack.pop() << endl;
    return 0;
}

#### 链式栈的实现

链式栈由一系列节点组成，每个节点包含数据和指向下一个节点的指针。栈顶是链表的第一个节点，通过维护一个指向栈顶的指针来实现。每次入栈时，创建一个新节点，将其插入链表头部；每次出栈时，返回头部节点的数据，并更新指针。

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

class LinkedStack {
private:
    Node* top;

public:
    LinkedStack() : top(nullptr) {}

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

    void push(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack is Empty" << endl;
            return -1;
        } else {
            Node* temp = top;
            int data = top->data;
            top = top->next;
            delete temp;
            return data;
        }
    }
};

int main() {
    LinkedStack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);

    cout << "Popped: " << stack.pop() << endl;
    cout << "Popped: " << stack.pop() << endl;
    return 0;
}

## 2.2 栈的算法应用

### 2.2.1 括号匹配问题

括号匹配问题是一个经典问题，经常用于演示栈的应用。算法的核心思想是，遍历输入的表达式，对于每个遇到的左括号，将其推入栈内；对于每个遇到的右括号，检查栈顶的左括号是否匹配。若匹配，则将左括号出栈；否则，表达式不匹配。最终检查栈是否为空，若为空则表达式正确匹配。

#### 实现括号匹配算法

#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string &str) {
    std::stack<char> stack;
    for (char ch : str) {
        switch (ch) {
            case '(':
            case '[':
            case '{':
                stack.push(ch);
                break;
            case ')':
                if (stack.empty() || stack.top() != '(') {
                    return false;
                }
                stack.pop();
                break;
            case ']':
                if (stack.empty() || stack.top() != '[') {
                    return false;
                }
                stack.pop();
                break;
            case '}':
                if (stack.empty() || stack.top() != '{') {
                    return false;
                }
                stack.pop();
                break;
        }
    }
    return stack.empty();
}

int main() {
    std::string str = "{()}[]";
    if (isBalanced(str)) {
        std::cout << "Balanced string" << std::endl;
    } else {
        std::cout << "Unbalanced string" << std::endl;
    }
    return 0;
}

### 2.2.2 函数调用栈

函数调用栈是栈在编程语言中的一个典型应用。在程序运行时，函数调用顺序被存储在一个称为调用栈的内部栈中。每次调用一个函数时，调用的上下文信息（包括局部变量、参数、返回地址等）被推入栈中。当函数执行完毕后，它的上下文信息从栈中弹出，并且程序返回到调用函数继续执行。

### 2.2.3 表达式求值

表达式求值通常涉及两个栈：一个用于数字（数值栈），另一个用于操作符（操作符栈）。算法根据操作符的优先级来决定何时从栈中弹出操作符，并执行相应的计算。

#### 表达式求值的伪代码

初始化两个栈：数值栈和操作符栈
对于表达式中的每个元素（可能为数字或操作符）：
    如果元素是数字：
        直接压入数值栈
    如果元素是操作符：
        如果操作符栈为空或栈顶操作符优先级低于当前操作符，则将当前操作符压入栈
        否则，从数值栈中弹出两个元素，从操作符栈中弹出栈顶操作符，
        执行操作，并将结果压入数值栈
        重复以上步骤直到当前操作符可以被压入操作符栈
如果表达式遍历完成，且操作符栈中仍有元素：
    弹出并处理剩余的操作符
返回数值栈中的最终结果

## 2.3 栈的高级应用场景

### 2.3.1 后缀表达式计算

后缀表达式（也称为逆波兰表示法）是一种没有括号，所有运算符置于操作数之后的算术表达式表示方法。利用栈来计算后缀表达式是非常高效的，算法只需遍历表达式一次，对于每个遇到的操作数或操作符，根据操作符决定如何处理栈顶元素。

### 2.3.2 迷宫问题的深度优先搜索（DFS）

深度优先搜索（DFS）是利用递归或栈来实现的一种图遍历算法，常用于解决迷宫问题。算法从起点开始，向一个方向探索直到无法前进，然后回溯到上一个分叉点，选择另一个方向继续探索，直到找到终点或遍历完所有路径。

迷宫问题中栈的应用通常表现在存储路径上，每次遇到死胡同时，回溯到上一个叉点并从栈中弹出上一个位置，继续探索其它路径。

本章节介绍了栈在解决各种问题时的基本操作和应用，包括算法示例以及实现思路的详细解释。在后续章节中，我们将探讨队列