• C++

  • C++ 栈(Stack)数据结构学习教程

  • @ 2025-7-10 20:34:16

栈（Stack）是一种遵循后进先出（Last In First Out，LIFO）原则的线性数据结构。就像一叠盘子，最后放上去的盘子总是最先被拿走。栈在计算机科学中有广泛应用，比如函数调用栈、表达式求值、浏览器历史记录等。下面我将从栈的基本概念开始，详细介绍栈的实现和应用。

C++ 栈(Stack)数据结构学习教程

1. 栈的基本概念

栈(Stack)是一种遵循**后进先出(LIFO, Last-In-First-Out)**原则的线性数据结构。就像一摞盘子，最后放上去的盘子总是最先被拿走。栈在计算机科学中有广泛应用，例如：

  • 函数调用的执行栈
  • 表达式求值（如逆波兰表达式）
  • 浏览器的后退功能
  • 回溯算法（如迷宫路径搜索）

2. 栈的核心操作

栈主要支持以下操作：

  • push(element)：将元素压入栈顶
  • pop()：移除栈顶元素
  • top()：返回栈顶元素
  • empty()：判断栈是否为空
  • size()：返回栈中元素的数量

3. C++实现栈的两种方式

方式一：使用数组实现静态栈

#include <iostream>
using namespace std;

template <typename T, int MAX_SIZE = 100>
class ArrayStack {
private:
    T data[MAX_SIZE];  // 存储栈中元素的数组
    int topIndex;      // 栈顶元素的索引，-1表示空栈

public:
    // 构造函数：初始化栈
    ArrayStack() : topIndex(-1) {}

    // 判断栈是否为空
    bool empty() const {
        return topIndex == -1;
    }

    // 返回栈的大小
    int size() const {
        return topIndex + 1;
    }

    // 压栈操作：将元素压入栈顶
    void push(const T& value) {
        if (topIndex >= MAX_SIZE - 1) {
            cerr << "Stack overflow!" << endl;
            exit(EXIT_FAILURE);
        }
        data[++topIndex] = value;
    }

    // 弹栈操作：移除栈顶元素
    void pop() {
        if (empty()) {
            cerr << "Stack underflow!" << endl;
            exit(EXIT_FAILURE);
        }
        --topIndex;
    }

    // 获取栈顶元素的引用
    T& top() {
        if (empty()) {
            cerr << "Stack is empty!" << endl;
            exit(EXIT_FAILURE);
        }
        return data[topIndex];
    }

    // 获取栈顶元素的常量引用（用于常量对象）
    const T& top() const {
        if (empty()) {
            cerr << "Stack is empty!" << endl;
            exit(EXIT_FAILURE);
        }
        return data[topIndex];
    }
};

方式二：使用链表实现动态栈

#include <iostream>
using namespace std;

// 链表节点的定义
template <typename T>
struct Node {
    T data;         // 节点存储的数据
    Node* next;     // 指向下一个节点的指针

    // 节点构造函数
    Node(const T& value) : data(value), next(nullptr) {}
};

template <typename T>
class LinkedStack {
private:
    Node<T>* topNode;  // 指向栈顶节点的指针
    int stackSize;     // 栈的大小

public:
    // 构造函数：初始化栈
    LinkedStack() : topNode(nullptr), stackSize(0) {}

    // 析构函数：释放栈中所有节点的内存
    ~LinkedStack() {
        while (!empty()) {
            pop();
        }
    }

    // 判断栈是否为空
    bool empty() const {
        return topNode == nullptr;
    }

    // 返回栈的大小
    int size() const {
        return stackSize;
    }

    // 压栈操作：在链表头部插入新节点
    void push(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        newNode->next = topNode;
        topNode = newNode;
        ++stackSize;
    }

    // 弹栈操作：删除链表头部节点
    void pop() {
        if (empty()) {
            cerr << "Stack underflow!" << endl;
            exit(EXIT_FAILURE);
        }
        Node<T>* temp = topNode;
        topNode = topNode->next;
        delete temp;
        --stackSize;
    }

    // 获取栈顶元素的引用
    T& top() {
        if (empty()) {
            cerr << "Stack is empty!" << endl;
            exit(EXIT_FAILURE);
        }
        return topNode->data;
    }

    // 获取栈顶元素的常量引用（用于常量对象）
    const T& top() const {
        if (empty()) {
            cerr << "Stack is empty!" << endl;
            exit(EXIT_FAILURE);
        }
        return topNode->data;
    }
};

4. 使用C++标准库中的栈

C++标准库已经提供了std::stack容器适配器，使用起来更加方便：

#include <iostream>
#include <stack>  // 包含栈的头文件

int main() {
    // 创建一个存储整数的栈
    std::stack<int> myStack;

    // 压栈操作
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    // 访问栈顶元素
    std::cout << "Top element: " << myStack.top() << std::endl;  // 输出: 30

    // 弹栈操作
    myStack.pop();
    std::cout << "Top element after pop: " << myStack.top() << std::endl;  // 输出: 20

    // 检查栈的大小
    std::cout << "Stack size: " << myStack.size() << std::endl;  // 输出: 2

    // 判断栈是否为空
    std::cout << "Is stack empty? " << (myStack.empty() ? "Yes" : "No") << std::endl;  // 输出: No

    return 0;
}

5. 栈的典型应用示例

示例1：括号匹配检查

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

bool isBalanced(const std::string& expression) {
    std::stack<char> s;
    for (char c : expression) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);  // 左括号入栈
        } else if (c == ')' || c == ']' || c == '}') {
            if (s.empty()) return false;  // 没有匹配的左括号
            char top = s.top();
            s.pop();
            // 检查括号类型是否匹配
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return s.empty();  // 如果栈为空，则所有括号都匹配
}

int main() {
    std::string expr1 = "{[()]}";  // 匹配
    std::string expr2 = "{[(])}";  // 不匹配
    std::cout << "Expression 1 is balanced: " << (isBalanced(expr1) ? "Yes" : "No") << std::endl;
    std::cout << "Expression 2 is balanced: " << (isBalanced(expr2) ? "Yes" : "No") << std::endl;
    return 0;
}

示例2：十进制转二进制

#include <iostream>
#include <stack>

std::string decimalToBinary(int num) {
    if (num == 0) return "0";
    
    std::stack<int> s;
    while (num > 0) {
        s.push(num % 2);  // 余数入栈
        num /= 2;
    }
    
    std::string result;
    while (!s.empty()) {
        result += std::to_string(s.top());  // 按顺序出栈组成二进制数
        s.pop();
    }
    return result;
}

int main() {
    int number = 25;
    std::cout << "Decimal: " << number << " -> Binary: " << decimalToBinary(number) << std::endl;
    // 输出: Decimal: 25 -> Binary: 11001
    return 0;
}

6. 栈的时间复杂度分析

  • push()：O(1)
  • pop()：O(1)
  • top()：O(1)
  • empty()：O(1)
  • size()：O(1)

无论是数组实现还是链表实现，栈的基本操作都能在常数时间内完成。

7. 总结

栈是一种非常基础但重要的数据结构，它的后进先出特性使其在处理需要逆序操作的场景中特别有用。通过本教程，你应该掌握了：

  1. 栈的基本概念和操作
  2. 如何用数组和链表实现栈
  3. 如何使用C++标准库中的栈
  4. 栈在实际问题中的应用

希望这篇教程能帮助你理解和掌握C++中的栈数据结构！

5 条评论

  • @ 2025-7-10 21:24:37 
    #include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isBalanced(string expr) {
	stack<char> s;//先创建一个栈
	
	for (char c : expr) {//遍历表达式字符串中的每一个字符
		if (c == '(' || c == '[' || c == '{') {//字符是左括号就放到栈里面去
			s.push(c);
		} else if (c == ')' || c == ']' || c == '}') {//否则如果是右括号，不要放进去，还要取出来
			if (s.empty()) return false;//栈是空的，直接判断表达式不合法
			
			char top = s.top();//获取栈顶的第一个左括号，刚刚放进去的
			s.pop();//把这个栈顶的第一个左括号删掉
			
			if ((c == ')' && top != '(') ||
				(c == ']' && top != '[') ||
				(c == '}' && top != '{')) {
				return false;
			}//如果不匹配，直接结束
			//否则匹配就继续
		}
		//不是括号就忽略
	}
	
	return s.empty();//判断栈是否为空，因为只有栈是空的，才全部匹配。
}

int main() {
	// 有效表达式测试
	cout << "有效表达式测试:" << endl;
	cout << "()  -> " << (isBalanced("()") ? "匹配" : "不匹配") << endl;
	cout << "[]  -> " << (isBalanced("[]") ? "匹配" : "不匹配") << endl;
	cout << "{}  -> " << (isBalanced("{}") ? "匹配" : "不匹配") << endl;
	cout << "()[]{}  -> " << (isBalanced("()[]{}") ? "匹配" : "不匹配") << endl;
	cout << "{[]}  -> " << (isBalanced("{[]}") ? "匹配" : "不匹配") << endl;
	cout << "([{}])  -> " << (isBalanced("([{}])") ? "匹配" : "不匹配") << endl;
	cout << "a(b[c]d)e  -> " << (isBalanced("a(b[c]d)e") ? "匹配" : "不匹配") << endl;
	cout << "((((()))))  -> " << (isBalanced("((((()))))") ? "匹配" : "不匹配") << endl;
	
	// 无效表达式测试
	cout << "\n无效表达式测试:" << endl;
	cout << "(  -> " << (isBalanced("(") ? "匹配" : "不匹配") << endl;
	
	cout << ")  -> " << (isBalanced(")") ? "匹配" : "不匹配") << endl;
	
	cout << "[)  -> " << (isBalanced("[)") ? "匹配" : "不匹配") << endl;
	cout << "([)]  -> " << (isBalanced("([)]") ? "匹配" : "不匹配") << endl;
	cout << "{[(]  -> " << (isBalanced("{[(]") ? "匹配" : "不匹配") << endl;
	cout << "((((((())  -> " << (isBalanced("((((((())") ? "匹配" : "不匹配") << endl;
	cout << "a(b[c}d)e  -> " << (isBalanced("a(b[c}d)e") ? "匹配" : "不匹配") << endl;
	
	return 0;
}
    • @ 2025-7-10 21:00:41

      括号匹配问题详解

      括号匹配问题是计算机科学中的经典问题，主要检验表达式中的括号是否正确配对和嵌套。具体来说，这个问题要求判断给定字符串中的括号是否满足以下条件：

      1. 每个左括号必须有对应的右括号
      2. 括号必须以正确的顺序闭合（例如，[()] 有效，但 [(]) 无效）
      3. 每种类型的括号必须正确匹配（( 对应 ), [ 对应 ], { 对应 }）

      测试样例

      以下是括号匹配问题的典型测试样例：

      有效表达式示例：

      1. ()
      2. []
      3. {}
      4. ()[]{}
      5. {[]}
      6. ([{}])
      7. a(b[c]d)e
      8. ((((()))))

      无效表达式示例：

      1. ( - 缺少右括号
      2. ) - 缺少左括号
      3. [) - 括号类型不匹配
      4. ([)] - 括号嵌套顺序错误
      5. {[()] - 缺少右括号
      6. ((((((()) - 括号数量不匹配
      7. a(b[c}d)e - 括号类型不匹配

      代码测试示例

      使用之前的 isBalanced 函数，可以测试上述所有样例：

      #include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isBalanced(string expr) {
    stack<char> s;
    
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (s.empty()) return false;
            
            char top = s.top();
            s.pop();
            
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    
    return s.empty();
}

int main() {
    // 有效表达式测试
    cout << "有效表达式测试:" << endl;
    cout << "()  -> " << (isBalanced("()") ? "匹配" : "不匹配") << endl;
    cout << "[]  -> " << (isBalanced("[]") ? "匹配" : "不匹配") << endl;
    cout << "{}  -> " << (isBalanced("{}") ? "匹配" : "不匹配") << endl;
    cout << "()[]{}  -> " << (isBalanced("()[]{}") ? "匹配" : "不匹配") << endl;
    cout << "{[]}  -> " << (isBalanced("{[]}") ? "匹配" : "不匹配") << endl;
    cout << "([{}])  -> " << (isBalanced("([{}])") ? "匹配" : "不匹配") << endl;
    cout << "a(b[c]d)e  -> " << (isBalanced("a(b[c]d)e") ? "匹配" : "不匹配") << endl;
    cout << "((((()))))  -> " << (isBalanced("((((()))))") ? "匹配" : "不匹配") << endl;

    // 无效表达式测试
    cout << "\n无效表达式测试:" << endl;
    cout << "(  -> " << (isBalanced("(") ? "匹配" : "不匹配") << endl;
    cout << ")  -> " << (isBalanced(")") ? "匹配" : "不匹配") << endl;
    cout << "[)  -> " << (isBalanced("[)") ? "匹配" : "不匹配") << endl;
    cout << "([)]  -> " << (isBalanced("([)]") ? "匹配" : "不匹配") << endl;
    cout << "{[(]  -> " << (isBalanced("{[(]") ? "匹配" : "不匹配") << endl;
    cout << "((((((())  -> " << (isBalanced("((((((())") ? "匹配" : "不匹配") << endl;
    cout << "a(b[c}d)e  -> " << (isBalanced("a(b[c}d)e") ? "匹配" : "不匹配") << endl;

    return 0;
}

      输出结果

      有效表达式测试:
()  -> 匹配
[]  -> 匹配
{}  -> 匹配
()[]{}  -> 匹配
{[]}  -> 匹配
([{}])  -> 匹配
a(b[c]d)e  -> 匹配
((((()))))  -> 匹配

无效表达式测试:
(  -> 不匹配
)  -> 不匹配
[)  -> 不匹配
([)]  -> 不匹配
{[(]  -> 不匹配
((((((())  -> 不匹配
a(b[c}d)e  -> 不匹配

      扩展应用

      括号匹配算法的变种包括：

      1. 处理不同类型的分隔符（如引号、尖括号等）
      2. 计算嵌套深度
      3. 修复不匹配的括号（如添加缺失的括号）

      这种算法在编译器语法检查、代码格式化工具和文本编辑器中都有实际应用。

      • @ 2025-7-10 20:57:26 
        #include <bits/stdc++.h>
using namespace std;
stack<int > s;
void Sss(int N, int d) {
	if (N == 0) {
		s.push(0);
	}
	while (N > 0) {
		s.push(N % d);
		N = N / d;
	}
}

int main() {
	int N, d;
	cin >> N;
	cin >> d;
	Sss(N, d);
	while (!s.empty()) {
		cout << s.top();
		s.pop();
	}
	return 0;
}
        • @ 2025-7-10 20:36:26

          C++ STL Stack学习教程

          在C++中，stack是标准模板库(STL)提供的一种容器适配器，它遵循后进先出(LIFO)的原则。下面我将为你详细介绍stack的使用方法。

          1. 什么是栈(Stack)？

          栈是一种特殊的数据结构，类似于一叠盘子。最后放上去的盘子总是最先被拿走，这就是后进先出(LIFO)的原则。栈提供了压入(push)、弹出(pop)、查看栈顶(top)等基本操作。

          2. stack的基本操作

          下面是一个简单的示例，展示了stack的基本操作：

          #include <iostream>
#include <stack>      // 包含stack头文件
using namespace std;  // 使用标准命名空间

int main() {
    // 1. 声明一个存储int类型的栈
    stack<int> s;

    // 2. 压入元素到栈中
    s.push(10);       // 栈底 -> 10
    s.push(20);       // 栈底 -> 10, 20
    s.push(30);       // 栈底 -> 10, 20, 30(栈顶)

    // 3. 查看栈顶元素
    cout << "栈顶元素是: " << s.top() << endl;  // 输出: 30

    // 4. 弹出栈顶元素
    s.pop();          // 弹出30，栈变为: 10, 20(栈顶)
    cout << "弹出后栈顶元素是: " << s.top() << endl;  // 输出: 20

    // 5. 检查栈是否为空
    if (s.empty()) {
        cout << "栈为空" << endl;
    } else {
        cout << "栈不为空，大小为: " << s.size() << endl;  // 输出: 2
    }

    // 6. 清空栈
    while (!s.empty()) {
        s.pop();
    }
    cout << "清空后栈的大小为: " << s.size() << endl;  // 输出: 0

    return 0;
}

          3. stack的常用方法

          方法 描述
          push(x) 将元素x压入栈顶
          pop() 移除栈顶元素，但不返回其值
          top() 返回栈顶元素的引用
          empty() 检查栈是否为空，为空返回true
          size() 返回栈中元素的数量

          4. 更复杂的示例

          下面是一个使用stack解决括号匹配问题的示例：

          #include <iostream>
#include <stack>
#include <string>
using namespace std;

// 检查括号是否匹配的函数
bool isBalanced(string expr) {
    stack<char> s;
    
    for (char c : expr) {
        // 如果是左括号，压入栈中
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        }
        // 如果是右括号
        else {
            if (s.empty()) {
                return false;  // 没有匹配的左括号
            }
            
            char top = s.top();
            s.pop();
            
            // 检查括号是否匹配
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    
    // 如果栈为空，说明所有括号都匹配
    return s.empty();
}

int main() {
    string expr1 = "{[()]}";  // 匹配
    string expr2 = "{[(])}";  // 不匹配
    
    cout << expr1 << " 是否匹配: " << (isBalanced(expr1) ? "是" : "否") << endl;
    cout << expr2 << " 是否匹配: " << (isBalanced(expr2) ? "是" : "否") << endl;
    
    return 0;
}

          5. stack的应用场景

          栈在计算机科学中有许多应用，包括：

          1. 函数调用栈：保存函数调用的上下文
          2. 表达式求值：计算后缀表达式(逆波兰表达式)
          3. 括号匹配检查：如上面的示例
          4. 浏览器的后退功能
          5. 编辑器的撤销操作

          6. 注意事项

          1. 栈的限制：stack不支持遍历操作，也不能随机访问元素。只能访问栈顶元素。
          2. 空栈操作：在调用top()和pop()之前，应确保栈不为空，否则会导致未定义行为。
          3. 性能考虑：stack的push、pop和top操作都是O(1)时间复杂度。

          7. 总结

          通过本教程，你学习了：

          • stack的基本概念和LIFO原则
          • stack的常用方法：push、pop、top、empty、size
          • 如何使用stack解决实际问题
          • stack的应用场景和注意事项

          栈是一个非常实用的数据结构，在算法和程序设计中有广泛的应用。掌握它将对你的编程能力有很大帮助。

          • @ 2025-7-10 20:35:14

            C++ Stack（栈）学习教程

            栈（Stack）是一种遵循**后进先出（LIFO, Last In First Out）**原则的线性数据结构。类比于现实生活中的一摞盘子，最后放上去的盘子总是最先被拿走。

            在C++中，栈可以通过多种方式实现，下面我将从最基础的数组实现开始，逐步讲解到STL标准库中的stack容器。

            1. 栈的基本概念与操作

            栈支持以下核心操作：

            • push：向栈顶添加元素（入栈）
            • pop：移除栈顶元素（出栈）
            • top：获取栈顶元素的值
            • empty：判断栈是否为空
            • size：返回栈中元素的数量

            2. 使用数组实现栈

            下面是一个基于数组的栈实现，包含详细注释：

            #include <iostream>
using namespace std;

template<typename T, int MAX_SIZE = 100>
class ArrayStack {
private:
    T data[MAX_SIZE];  // 存储栈中元素的数组
    int topIndex;      // 栈顶元素的索引，-1表示栈为空

public:
    // 构造函数，初始化栈
    ArrayStack() : topIndex(-1) {}

    // 入栈操作：将元素添加到栈顶
    bool push(const T& value) {
        if (topIndex >= MAX_SIZE - 1) {
            cout << "栈溢出！无法添加元素 " << value << endl;
            return false;
        }
        data[++topIndex] = value;  // 先增加索引，再赋值
        return true;
    }

    // 出栈操作：移除栈顶元素
    bool pop() {
        if (empty()) {
            cout << "栈为空！无法执行pop操作" << endl;
            return false;
        }
        --topIndex;  // 直接减少索引，下次push时会覆盖原有值
        return true;
    }

    // 获取栈顶元素的引用
    T& top() {
        if (empty()) {
            throw runtime_error("栈为空！无法获取栈顶元素");
        }
        return data[topIndex];
    }

    // 获取栈顶元素的常量引用（用于const对象）
    const T& top() const {
        if (empty()) {
            throw runtime_error("栈为空！无法获取栈顶元素");
        }
        return data[topIndex];
    }

    // 判断栈是否为空
    bool empty() const {
        return topIndex == -1;
    }

    // 返回栈的当前大小
    int size() const {
        return topIndex + 1;
    }

    // 打印栈中所有元素（从栈底到栈顶）
    void print() const {
        cout << "栈内容（从栈底到栈顶）: ";
        for (int i = 0; i <= topIndex; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    }
};

            使用示例：

            int main() {
    ArrayStack<int> stack;

    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    cout << "栈顶元素: " << stack.top() << endl;  // 输出: 30
    stack.print();  // 输出: 栈内容（从栈底到栈顶）: 10 20 30

    stack.pop();
    cout << "执行一次pop后，栈顶元素: " << stack.top() << endl;  // 输出: 20
    
    return 0;
}

            3. 使用链表实现栈

            基于链表的栈实现可以动态调整大小，避免栈溢出问题：

            #include <iostream>
using namespace std;

template<typename T>
class LinkedStack {
private:
    // 链表节点结构
    struct Node {
        T data;         // 节点存储的数据
        Node* next;     // 指向下一个节点的指针

        Node(const T& value) : data(value), next(nullptr) {}
    };

    Node* topNode;      // 栈顶节点指针
    int stackSize;      // 栈的当前大小

public:
    // 构造函数
    LinkedStack() : topNode(nullptr), stackSize(0) {}

    // 析构函数：释放所有节点的内存
    ~LinkedStack() {
        while (!empty()) {
            pop();
        }
    }

    // 入栈操作
    void push(const T& value) {
        Node* newNode = new Node(value);
        newNode->next = topNode;  // 新节点指向原来的栈顶
        topNode = newNode;        // 更新栈顶指针
        ++stackSize;
    }

    // 出栈操作
    bool pop() {
        if (empty()) {
            cout << "栈为空！无法执行pop操作" << endl;
            return false;
        }
        Node* temp = topNode;     // 保存当前栈顶节点
        topNode = topNode->next;  // 更新栈顶指针
        delete temp;              // 释放原栈顶节点的内存
        --stackSize;
        return true;
    }

    // 获取栈顶元素的引用
    T& top() {
        if (empty()) {
            throw runtime_error("栈为空！无法获取栈顶元素");
        }
        return topNode->data;
    }

    // 获取栈顶元素的常量引用
    const T& top() const {
        if (empty()) {
            throw runtime_error("栈为空！无法获取栈顶元素");
        }
        return topNode->data;
    }

    // 判断栈是否为空
    bool empty() const {
        return topNode == nullptr;
    }

    // 返回栈的大小
    int size() const {
        return stackSize;
    }

    // 打印栈中所有元素（从栈顶到栈底）
    void print() const {
        cout << "栈内容（从栈顶到栈底）: ";
        Node* current = topNode;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
};

            4. 使用C++ STL中的stack容器

            C++标准库提供了std::stack容器适配器，它基于其他容器（默认是deque）实现栈的功能：

            #include <iostream>
#include <stack>  // 包含stack头文件
using namespace std;

int main() {
    // 创建一个存储整数的栈
    stack<int> st;

    // 入栈操作
    st.push(10);
    st.push(20);
    st.push(30);

    // 访问栈顶元素
    cout << "栈顶元素: " << st.top() << endl;  // 输出: 30

    // 出栈操作
    st.pop();
    cout << "执行pop后，栈顶元素: " << st.top() << endl;  // 输出: 20

    // 检查栈是否为空
    cout << "栈是否为空? " << (st.empty() ? "是" : "否") << endl;  // 输出: 否

    // 获取栈的大小
    cout << "栈的大小: " << st.size() << endl;  // 输出: 2

    return 0;
}

            5. 栈的应用场景

            栈在计算机科学中有广泛的应用，例如：

            1. 函数调用栈：记录函数调用的上下文，保存返回地址和局部变量
            2. 表达式求值：计算后缀表达式（逆波兰表达式）
            3. 括号匹配检查：验证表达式中括号是否正确匹配
            4. 浏览器历史记录：后退功能使用栈结构
            5. DFS（深度优先搜索）：递归实现或显式栈实现

            6. 常见面试题

            1. 如何实现一个支持min()操作的栈？

              • 可以使用两个栈，一个存储数据，另一个存储当前最小值。

            2. 如何用两个队列实现一个栈？

              • 入栈操作：将元素添加到非空队列
              • 出栈操作：将非空队列的前n-1个元素移到另一个队列，最后一个元素出队

            3. 如何判断括号字符串是否有效？

              • 使用栈遍历字符串，遇到左括号入栈，遇到右括号时弹出栈顶元素检查匹配。

            通过以上内容，你应该对C++中栈的实现和使用有了全面的了解。建议动手编写代码，加深对栈这种数据结构的理解。

            • 1
            436
            已通过
            0
            题解被赞
            1. 关于
            2. 联系我们
            3. 隐私
            4. 服务条款
            5. 版权申诉
            6. Language
            7. 兼容模式
            8. 主题
            4. 在线咨询
            5. Worker 0, 32ms
            6. Powered by Hydro v4.13.3 Community