C++以队列为工具,实现栈元素的逆置
时间: 2024-04-29 16:22:22 浏览: 6
可以通过两个队列来实现栈元素的逆置。
具体实现步骤如下:
1. 定义两个队列Q1和Q2,Q1用于存储栈中的元素,Q2用于辅助操作。
2. 当需要将一个元素入栈时,将其加入到Q1队尾。
3. 当需要将栈顶元素出栈时,先将Q1中的所有元素依次出队并加入到Q2队尾,直到Q1中只剩下一个元素,此时将该元素出队即可。
4. 当需要对栈中的元素进行逆置时,依次将Q1中的所有元素出队并加入到Q2队尾,直到Q1中只剩下一个元素,将该元素出队并加入到Q2队尾,此时Q2中存储的元素顺序与原来的Q1中相反,将Q2赋值给Q1即可完成元素逆置。
下面是实现代码示例:
```cpp
#include <iostream>
#include <queue>
using namespace std;
class MyStack {
private:
queue<int> q1;
queue<int> q2;
public:
/** Push element x onto stack. */
void push(int x) {
q1.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
while (q1.size() > 1) {
q2.push(q1.front());
q1.pop();
}
int res = q1.front();
q1.pop();
swap(q1, q2);
return res;
}
/** Get the top element. */
int top() {
while (q1.size() > 1) {
q2.push(q1.front());
q1.pop();
}
int res = q1.front();
q2.push(res);
q1.pop();
swap(q1, q2);
return res;
}
/** Returns whether the stack is empty. */
bool empty() {
return q1.empty();
}
/** Reverse the elements in the stack */
void reverse() {
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
swap(q1, q2);
}
};
int main() {
MyStack s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
cout << "Before reverse: " << endl;
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
s.reverse();
cout << "\nAfter reverse: " << endl;
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
return 0;
}
```
输出结果为:
```
Before reverse:
5 4 3 2 1
After reverse:
1 2 3 4 5
```