21xrx.com
2025-03-27 00:55:35 Thursday
文章检索 我的文章 写文章
C++实现栈判断出栈顺序是否正确的代码
2023-06-29 01:01:48 深夜i     --     --
C++ 栈 判断 出栈顺序 代码

在C++中，实现一个栈并判断出栈顺序是否正确是一个常见的问题。在本篇文章中，我们将探讨如何实现这个功能的代码。

首先，需要了解栈的特点，它遵循“后进先出”的原则。也就是说，每次只有最后添加的元素可以被移除。因此，栈顺序的正确性取决于元素的添加与移除顺序。

下面是一个简单的使用vector实现的栈类：

#include <vector>
using namespace std;
class Stack {
public:
  void push(int x) {
    elems.push_back(x);
  }
  
  int top() {
    return elems.back();
  }
  
  void pop() {
    elems.pop_back();
  }
  
  bool empty() {
    return elems.empty();
  }
  
private:
  vector<int> elems;
};

这里的“push”函数用于将元素添加到栈中，“top”函数用于获取栈顶元素，“pop”函数用于移除栈顶元素，“empty”函数用于判断栈是否为空。

现在，我们需要编写一个函数来判断给定的出栈序列是否与入栈序列匹配。下面是该函数的实现：

bool checkStackSequence(const vector<int>& pushSeq, const vector<int>& popSeq) {
  Stack s; // 创建一个栈实例
  int pushIdx = 0; // 入栈序列下标
  int popIdx = 0; // 出栈序列下标
  while (pushIdx < pushSeq.size()) {
    s.push(pushSeq[pushIdx++]); // 将元素依次添加到栈中
    while (!s.empty() && s.top() == popSeq[popIdx]) {
      // 当栈不为空且栈顶元素与出栈序列元素相同时，执行出栈操作
      s.pop();
      popIdx++; // 更新出栈序列下标
    }
  }
  return s.empty(); // 如果最后栈为空，说明出栈序列与入栈序列匹配
}

在这个函数中，我们使用了两个变量来跟踪入栈和出栈序列的下标。我们依次将入栈序列中的元素添加到栈中，然后不断检查栈顶元素是否与出栈序列中的下一个元素匹配。如果匹配，就执行出栈操作并更新出栈序列下标。如果最后栈为空，就说明出栈序列与入栈序列匹配，返回true，否则返回false。

为了测试这个函数，我们可以编写以下代码：

int main() {
  vector<int> pushSeq = 4;
  vector<int> popSeq1 = 2;
  vector<int> popSeq2 = 4;
  
  bool res1 = checkStackSequence(pushSeq, popSeq1); // 返回true
  bool res2 = checkStackSequence(pushSeq, popSeq2); // 返回false
  
  return 0;
}

在这个测试中，我们使用了两个不同的出栈序列来测试函数的正确性。第一个出栈序列与入栈序列匹配，因此返回true，而第二个出栈序列与入栈序列不匹配，返回false。

综上所述，这是一个简单而有效的方法来判断栈的出栈顺序是否正确的代码。

  
  

评论区