C++实现栈的逆置 |21xrx.com

C++实现栈的逆置

2023-06-29 21:33:40 深夜i -- --

C++ 栈逆置

栈是一种十分常见的数据结构，它通常被用来实现逆序输出、括号匹配等功能。但有时我们需要将一个已有的栈逆序，这时可以采取栈的弹出压入操作，但会破坏原有的栈结构，因此我们需要另外一个栈来辅助实现逆置。下面来介绍一下C++实现栈的逆置的方法。

首先，我们需要定义一个栈类，包括定义栈大小、栈顶指针以及栈元素等属性。然后定义栈的基本操作，如入栈、出栈、判断栈是否为空等。

接下来，我们需要定义一个函数，用来实现栈的逆置。这个函数接受原始栈作为输入，并通过入栈、出栈的操作实现栈的逆置。具体实现过程如下：

（1）定义一个新栈，用来存放逆置后的元素

（2）从原始栈中循环弹出元素，直到原始栈为空。在弹出的同时，将元素压入新栈中

（3）新栈的栈顶元素即为原始栈的底部元素，将其弹出并保存

（4）重复步骤（2）、（3），直到新栈为空

（5）将保存的原始栈底部元素压入原始栈中，逆置完成

代码实现如下：


#include <iostream>
#include <stack>
using namespace std;
void reverseStack(stack<int>& s) {
  stack<int> temp;
  while (!s.empty()) {
    temp.push(s.top());
    s.pop();
  }
  int bottom = temp.top(); //保存原始栈底部元素
  temp.pop();
  while (!temp.empty()) {
    s.push(temp.top());
    temp.pop();
  }
  s.push(bottom); //将底部元素压入原始栈中
}
int main() {
  stack<int> s;
  s.push(1);
  s.push(2);
  s.push(3);
  s.push(4);
  s.push(5);
  reverseStack(s);
  while (!s.empty()) {
    cout << s.top() << " ";
    s.pop();
  }
  return 0;
}

运行结果为：

1 2 3 4 5

通过以上代码，我们可以看到原始栈已经被逆置了。因为原始栈被操作过，所以在实际使用时，需要根据情况决定是否需要保留原始栈。

总之，通过以上实现方法可以实现C++栈的逆置，不仅保留了原有的栈结构，而且也可以实现快速地将栈进行逆序输出。这种思想可以应用在很多算法中，比如括号匹配和字符串逆置等。

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

下一篇: 《数据结构c++版第二版答案》- 李根强

评论区

()

相似文章