C++STL栈stack操作与应用实例-C++-PHP中文网

C++STL栈stack操作与应用实例

P粉602998670

发布： 2025-09-15 10:03:01

原创

545人浏览过

C++ STL栈stack提供后进先出的数据结构，支持push、pop、top、empty和size操作，适用于表达式求值、浏览器前进后退、括号匹配等场景，但不具线程安全性，需用互斥锁保证多线程安全。

c++stl栈stack操作与应用实例

C++ STL 栈 stack 提供了一种后进先出（LIFO）的数据结构，用于管理元素的顺序。它主要用于需要回溯、撤销或跟踪历史记录的场景。

栈 stack 的操作包括：

```
push(element)
```
登录后复制
: 将元素压入栈顶。
```
pop()
```
登录后复制
: 移除栈顶元素。
```
top()
```
登录后复制
: 返回栈顶元素（但不移除）。
```
empty()
```
登录后复制
: 检查栈是否为空。
```
size()
```
登录后复制
: 返回栈中元素的数量。

#include <iostream>
#include <stack>

int main() {
  std::stack<int> myStack;

  myStack.push(10);
  myStack.push(20);
  myStack.push(30);

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

  myStack.pop(); // 移除栈顶元素

  std::cout << "栈顶元素: " << myStack.top() << std::endl; // 输出 20

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

  while (!myStack.empty()) {
    std::cout << "栈顶元素: " << myStack.top() << std::endl;
    myStack.pop();
  }

  std::cout << "栈是否为空: " << myStack.empty() << std::endl; // 输出 1 (true)

  return 0;
}

登录后复制

C++ STL 栈 stack 在实际编程中有很多应用场景，下面介绍几个常见的例子。

如何使用 C++ STL 栈 stack 实现表达式求值？

立即学习“C++免费学习笔记（深入）”；

表达式求值是一个经典的栈的应用。我们可以使用两个栈，一个操作数栈和一个运算符栈。从左到右扫描表达式：

如果遇到操作数，则将其压入操作数栈。
如果遇到运算符，则：
- 如果运算符栈为空，或者当前运算符的优先级高于栈顶运算符的优先级，则将当前运算符压入运算符栈。
- 否则，弹出运算符栈顶的运算符，从操作数栈中弹出两个操作数，执行运算，将结果压入操作数栈，然后重复步骤 2。
扫描完成后，如果运算符栈不为空，则依次弹出运算符，从操作数栈中弹出两个操作数，执行运算，将结果压入操作数栈。
最后，操作数栈中剩下的唯一元素就是表达式的结果。

#include <iostream>
#include <stack>
#include <string>
#include <cctype> // isdigit

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

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

int evaluateExpression(const std::string& expression) {
  std::stack<int> operands;
  std::stack<char> operators;

  for (size_t i = 0; i < expression.length(); ++i) {
    if (isspace(expression[i])) continue;

    if (isdigit(expression[i])) {
      int num = 0;
      while (i < expression.length() && isdigit(expression[i])) {
        num = num * 10 + (expression[i] - '0');
        i++;
      }
      i--; // 回退一个字符，因为循环会再次递增
      operands.push(num);
    } else if (expression[i] == '(') {
      operators.push(expression[i]);
    } else if (expression[i] == ')') {
      while (!operators.empty() && operators.top() != '(') {
        char op = operators.top();
        operators.pop();
        int b = operands.top();
        operands.pop();
        int a = operands.top();
        operands.pop();
        operands.push(evaluate(a, b, op));
      }
      operators.pop(); // Pop the '('
    } else {
      while (!operators.empty() && precedence(expression[i]) <= precedence(operators.top())) {
        char op = operators.top();
        operators.pop();
        int b = operands.top();
        operands.pop();
        int a = operands.top();
        operands.pop();
        operands.push(evaluate(a, b, op));
      }
      operators.push(expression[i]);
    }
  }

  while (!operators.empty()) {
    char op = operators.top();
    operators.pop();
    int b = operands.top();
    operands.pop();
    int a = operands.top();
    operands.pop();
    operands.push(evaluate(a, b, op));
  }

  return operands.top();
}

int main() {
  std::string expression = "10 + 2 * (6 - (3 + 1))";
  std::cout << expression << " = " << evaluateExpression(expression) << std::endl;
  return 0;
}

登录后复制

如何使用 C++ STL 栈 stack 实现浏览器的前进后退功能？

这个挺常见的，后退用一个栈，前进用另一个栈。当用户访问一个新的页面时，将当前页面压入后退栈，并清空前进栈。当用户点击后退按钮时，从后退栈中弹出一个页面，并将其压入前进栈。当用户点击前进按钮时，从前进栈中弹出一个页面，并将其压入后退栈。

AppMall应用商店

AI应用商店，提供即时交付、按需付费的人工智能应用服务

查看详情

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

class BrowserHistory {
public:
  std::stack<std::string> backStack;
  std::stack<std::string> forwardStack;
  std::string currentPage;

  BrowserHistory(std::string homepage) : currentPage(homepage) {}

  void visit(std::string url) {
    backStack.push(currentPage);
    currentPage = url;
    while (!forwardStack.empty()) {
      forwardStack.pop();
    }
  }

  std::string back(int steps) {
    while (steps > 0 && !backStack.empty()) {
      forwardStack.push(currentPage);
      currentPage = backStack.top();
      backStack.pop();
      steps--;
    }
    return currentPage;
  }

  std::string forward(int steps) {
    while (steps > 0 && !forwardStack.empty()) {
      backStack.push(currentPage);
      currentPage = forwardStack.top();
      forwardStack.pop();
      steps--;
    }
    return currentPage;
  }

  std::string getCurrentPage() {
    return currentPage;
  }
};

int main() {
  BrowserHistory browser("google.com");
  browser.visit("baidu.com");
  browser.visit("youtube.com");
  std::cout << "Current page: " << browser.getCurrentPage() << std::endl; // youtube.com
  std::cout << "Back to: " << browser.back(1) << std::endl; // baidu.com
  std::cout << "Back to: " << browser.back(1) << std::endl; // google.com
  std::cout << "Forward to: " << browser.forward(1) << std::endl; // baidu.com
  std::cout << "Current page: " << browser.getCurrentPage() << std::endl; // baidu.com
  return 0;
}

登录后复制

C++ STL 栈 stack 在算法题中如何应用？

栈在解决算法问题中非常有用，特别是在处理涉及回溯、深度优先搜索（DFS）或需要维护特定顺序的问题时。

举个例子，括号匹配问题。给定一个包含括号的字符串，判断其中的括号是否匹配。可以使用栈来解决这个问题。遍历字符串，如果遇到左括号，则将其压入栈中。如果遇到右括号，则判断栈是否为空，如果为空，则说明右括号没有匹配的左括号，返回 false。否则，弹出栈顶的左括号，判断其是否与当前的右括号匹配，如果不匹配，则返回 false。遍历完成后，如果栈为空，则说明所有括号都匹配，返回 true。否则，说明有左括号没有匹配的右括号，返回 false。

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

bool isValid(std::string s) {
  std::stack<char> parentheses;
  for (char c : s) {
    switch (c) {
      case '(':
      case '[':
      case '{':
        parentheses.push(c);
        break;
      case ')':
        if (parentheses.empty() || parentheses.top() != '(') return false;
        parentheses.pop();
        break;
      case ']':
        if (parentheses.empty() || parentheses.top() != '[') return false;
        parentheses.pop();
        break;
      case '}':
        if (parentheses.empty() || parentheses.top() != '{') return false;
        parentheses.pop();
        break;
    }
  }
  return parentheses.empty();
}

int main() {
  std::string s1 = "(){}[]";
  std::string s2 = "([)]";
  std::cout << s1 << " is valid: " << isValid(s1) << std::endl; // 1 (true)
  std::cout << s2 << " is valid: " << isValid(s2) << std::endl; // 0 (false)
  return 0;
}

登录后复制

C++ STL 栈 stack 的线程安全性如何？

C++ STL 栈 stack 本身不是线程安全的。如果多个线程同时访问同一个栈，可能会导致数据竞争和未定义的行为。

为了在多线程环境中使用栈，需要采取适当的同步机制，例如互斥锁（mutex）。每个线程在访问栈之前，需要先获取互斥锁，访问完成后再释放互斥锁，以确保同一时间只有一个线程可以访问栈。

#include <iostream>
#include <stack>
#include <thread>
#include <mutex>

std::stack<int> myStack;
std::mutex stackMutex;

void pushToStack(int value) {
  std::lock_guard<std::mutex> lock(stackMutex); // RAII 风格的锁
  myStack.push(value);
  std::cout << "Thread " << std::this_thread::get_id() << " pushed " << value << std::endl;
}

int main() {
  std::thread t1(pushToStack, 10);
  std::thread t2(pushToStack, 20);

  t1.join();
  t2.join();

  std::cout << "Stack size: " << myStack.size() << std::endl;
  return 0;
}

登录后复制

以上就是C++STL栈stack操作与应用实例的详细内容，更多请关注php中文网其它相关文章！