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

原创

ithorizon 6个月前 (10-19) 阅读数 22 #后端开发

C++数据结构学习之栈的应用

一、引言

栈（Stack）是一种常用的数据结构，它遵循先入后出（First In Last Out，FILO）的原则。在C++中，栈的应用非常广泛，如表达式求值、括号匹配、递归调用等。本文将详细介绍C++数据结构中栈的应用，帮助初学者更好地懂得和掌握栈的使用。

二、栈的基本概念

栈是一种线性表，允许在一端进行插入和删除操作。栈的操作核心有两种：入栈（push）和出栈（pop）。栈顶元素是最先插入的元素，也是最后被删除的元素。栈底是栈的另一个端，不允许进行插入和删除操作。

三、栈的实现

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


#include 
using namespace std;
#define 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(T element) {
        if (isFull()) {
            cout << "栈已满，无法入栈" << endl;
            return;
        }
        stack[++top] = element;
    }
    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 
#include 
using namespace std;
double evaluateReversePolishExpression(string expression) {
    stack stack;
    istringstream iss(expression);
    string token;
    while (iss >> token) {
        if (token == "+") {
            double a = stack.top();
            stack.pop();
            double b = stack.top();
            stack.pop();
            stack.push(b + a);
        } else if (token == "-") {
            double a = stack.top();
            stack.pop();
            double b = stack.top();
            stack.pop();
            stack.push(b - a);
        } else if (token == "*") {
            double a = stack.top();
            stack.pop();
            double b = stack.top();
            stack.pop();
            stack.push(b * a);
        } else if (token == "/") {
            double a = stack.top();
            stack.pop();
            double b = stack.top();
            stack.pop();
            stack.push(b / a);
        } else {
            stack.push(stod(token));
        }
    }
    return stack.top();
}
int main() {
    string expression = "3 4 + 5 * 6 -";
    cout << "Result: " << evaluateReversePolishExpression(expression) << endl;
    return 0;
}

2. 括号匹配

栈可以用于检查括号是否匹配。以下是一个简洁的括号匹配示例：


#include 
#include 
#include 
using namespace std;
bool checkBrackets(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();
}
int main() {
    string expression = "{[()]}";
    cout << "Brackets match: " << (checkBrackets(expression) ? "Yes" : "No") << endl;
    return 0;
}