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

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

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

栈 stack 的操作包括：

• push(element)

  : 将元素压入栈顶。

• pop()

  : 移除栈顶元素。

• top()

  : 返回栈顶元素（但不移除）。

• empty()

  : 检查栈是否为空。

• size()

  : 返回栈中元素的数量。

#include 
#include 

int main() {
  std::stack 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++免费学习笔记（深入）”；

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

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

#include 
#include 
#include 
#include  // 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 operands;
  std::stack 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 实现浏览器的前进后退功能？

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

LongShot

LongShot 是一款 AI 写作助手，可帮助您生成针对搜索引擎优化的内容博客。

下载

#include 
#include 
#include 

class BrowserHistory {
public:
  std::stack backStack;
  std::stack 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 
#include 
#include 

bool isValid(std::string s) {
  std::stack 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 
#include 
#include 
#include 

std::stack myStack;
std::mutex stackMutex;

void pushToStack(int value) {
  std::lock_guard 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;
}