C++数据结构学习之栈的应用(C++数据结构入门：栈的应用详解)

一、引言

栈（Stack）是一种常见的数据结构，它遵循先入后出（First In Last Out，FILO）的原则。在C++中，栈的应用非常广泛，例如表达式求值、括号匹配、递归算法等。本文将详细介绍C++中栈的应用及其实现方法。

二、栈的基本概念

栈是一种线性表，其特点是只能在表的一端进行插入和删除操作。栈的操作关键有两种：压栈（push）和出栈（pop）。栈顶（top）是允许插入和删除的一端，栈底（bottom）是另一端。

三、栈的C++实现

在C++中，可以使用数组或链表来实现栈。以下是一个使用数组实现的栈的简洁示例：

#include 
using namespace std;
const int MAX_SIZE = 100; // 栈的最大容量
template 
class Stack {
private:
    T stack[MAX_SIZE]; // 存储栈元素的数组
    int top; // 栈顶位置
public:
    Stack() : top(-1) {} // 构造函数
    bool isEmpty() {
        return top == -1;
    }
    bool isFull() {
        return top == MAX_SIZE - 1;
    }
    void push(const T& item) {
        if (isFull()) {
            cout << "栈已满，无法插入元素！" << endl;
            return;
        }
        stack[++top] = item;
    }
    T pop() {
        if (isEmpty()) {
            cout << "栈为空，无法删除元素！" << endl;
            return T(); // 返回类型T的默认值
        }
        return stack[top--];
    }
    T getTop() {
        if (isEmpty()) {
            cout << "栈为空，无法获取栈顶元素！" << endl;
            return T(); // 返回类型T的默认值
        }
        return stack[top];
    }
};

四、栈的应用示例

1. 表达式求值

表达式求值是栈的一个经典应用。以下是一个简洁的表达式求值程序，它只赞成加减乘除四种运算符和整数：

#include 
#include 
#include 
using namespace std;
int evaluateExpression(const string& expression) {
    stack values;
    stack ops;
    for (int i = 0; i < expression.length(); i++) {
        if (expression[i] == ' ') {
            continue;
        } else if (expression[i] >= '0' && expression[i] <= '9') {
            int value = 0;
            while (i < expression.length() && expression[i] >= '0' && expression[i] <= '9') {
                value = value * 10 + (expression[i] - '0');
                i++;
            }
            values.push(value);
            i--;
        } else if (expression[i] == '(') {
            ops.push(expression[i]);
        } else if (expression[i] == ')') {
            while (!ops.empty() && ops.top() != '(') {
                int val2 = values.top();
                values.pop();
                int val1 = values.top();
                values.pop();
                char op = ops.top();
                ops.pop();
                switch (op) {
                    case '+': values.push(val1 + val2); break;
                    case '-': values.push(val1 - val2); break;
                    case '*': values.push(val1 * val2); break;
                    case '/': values.push(val1 / val2); break;
                }
            }
            ops.pop();
        } else {
            while (!ops.empty() && getPrecedence(ops.top()) >= getPrecedence(expression[i])) {
                int val2 = values.top();
                values.pop();
                int val1 = values.top();
                values.pop();
                char op = ops.top();
                ops.pop();
                switch (op) {
                    case '+': values.push(val1 + val2); break;
                    case '-': values.push(val1 - val2); break;
                    case '*': values.push(val1 * val2); break;
                    case '/': values.push(val1 / val2); break;
                }
            }
            ops.push(expression[i]);
        }
    }
    while (!ops.empty()) {
        int val2 = values.top();
        values.pop();
        int val1 = values.top();
        values.pop();
        char op = ops.top();
        ops.pop();
        switch (op) {
            case '+': values.push(val1 + val2); break;
            case '-': values.push(val1 - val2); break;
            case '*': values.push(val1 * val2); break;
            case '/': values.push(val1 / val2); break;
        }
    }
    return values.top();
}
int getPrecedence(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    }
    return 0;
}

2. 括号匹配

括号匹配是栈的另一个典型应用。以下是一个检查括号是否匹配的程序：

#include 
#include 
#include 
using namespace std;
bool areBracketsBalanced(const string& expression) {
    stack stack;
    for (char ch : expression) {
        if (ch == '(' || ch == '{' || ch == '[') {
            stack.push(ch);
        } else if (ch == ')' || ch == '}' || ch == ']') {
            if (stack.empty()) {
                return false;
            }
            char top = stack.top();
            stack.pop();
            if ((ch == ')' && top != '(') ||
                (ch == '}' && top != '{') ||
                (ch == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.empty();
}

3. 递归算法

递归算法是栈的一个隐含应用。递归函数的实现实际上使用了系统的调用栈来存储函数调用的状态。以下是一个经典的递归函数，用于计算斐波那契数列：

#include 
using namespace std;
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

五、总结

栈是一种非常实用的数据结构，其应用场景广泛。通过本文的介绍，我们了解了栈的基本概念、C++实现方法以及几个典型的应用示例。掌握栈的应用不仅可以尽大概减少损耗编程能力，还有助于明白更纷乱的数据结构和算法。

本文由IT视界版权所有,禁止未经同意的情况下转发