C++代码：判断栈的出栈顺序是否正确 |21xrx.com

C++代码：判断栈的出栈顺序是否正确

2023-07-04 00:51:41 深夜i -- --

C++ 栈出栈顺序判断正确

在C++编程中，栈是一种非常常见的数据结构，常用于实现函数调用、表达式求值等操作。当我们使用栈时，相信很多人都会注意到一个问题：如何判断一个栈的出栈顺序是否正确呢？

对于这个问题，我们可以利用栈的特性来实现一种简单的判断方法。具体来说，我们可以维护一个辅助栈，遍历输入的出栈序列，如果当前元素等于栈顶元素，则将栈顶元素弹出；否则就将入栈序列中的元素依次压入辅助栈中。最后，若辅助栈为空，则说明出栈顺序正确；否则，说明出栈顺序存在问题。

下面，我们来看一下具体的C++实现代码：


#include <iostream>
#include <stack>
using namespace std;
bool checkOrder(int pushArr[], int popArr[], int len) {
  stack<int> stk;
  int j = 0;
  for(int i = 0; i < len; i++) {
    stk.push(pushArr[i]);
    while(!stk.empty() && stk.top() == popArr[j]) {
      stk.pop();
      j++;
    }
  }
  return stk.empty();
}
int main() {
  int pushArr[] = 2;
  int popArr1[] = 2; //正确的出栈顺序
  int popArr2[] = 2; //错误的出栈顺序
  int len = 5;
  cout << checkOrder(pushArr, popArr1, len) << endl; //输出1，表示正确
  cout << checkOrder(pushArr, popArr2, len) << endl; //输出0，表示错误
  return 0;
}

在代码中，我们通过一个bool类型的函数checkOrder来实现了上述的判断逻辑。主函数中，我们分别测试了两个出栈序列，输出结果可以清晰地指出，哪一个是正确的出栈顺序，哪一个是错误的出栈顺序。

总之，判断栈的出栈顺序是否正确，只需要利用辅助栈的特性，实现上述的简单判断算法即可。这种方法简单易懂，适用于大多数场景，对于C++开发者来说，是一种非常实用的技巧。

上一篇: idea打包java可执行jar包

下一篇: 用C++实现图片转视频功能

评论区

()

相似文章