用队列表示栈
时间: 2023-07-19 15:13:01 浏览: 41
可以使用队列来实现栈的操作。具体做法是,使用两个队列,一个主队列和一个辅助队列。主队列用于存储栈中的元素,辅助队列用于在压入元素时辅助转移元素。
在压入元素时,将元素先插入到辅助队列中,然后将主队列中的所有元素出队并依次插入到辅助队列中,最后将辅助队列中的所有元素依次插入到主队列中。这样就可以实现栈的“先进后出”特性。
在弹出元素时,只需要从主队列中出队即可。
以下是示例代码实现:
```
class Stack {
private:
queue<int> q1, q2; // 使用两个队列
public:
void push(int x) {
q2.push(x); // 将元素插入到辅助队列中
// 将主队列中的所有元素依次插入到辅助队列中
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
// 将辅助队列中的所有元素依次插入到主队列中
while (!q2.empty()) {
q1.push(q2.front());
q2.pop();
}
}
int pop() {
int x = q1.front();
q1.pop();
return x;
}
bool empty() {
return q1.empty();
}
};
```
使用该类来操作栈时,可以先创建一个 Stack 对象,然后调用 push 和 pop 方法来压入和弹出元素,调用 empty 方法来判断栈是否为空。例如:
```
Stack s;
s.push(1);
s.push(2);
s.push(3);
cout << s.pop() << endl; // 输出 3
cout << s.pop() << endl; // 输出 2
cout << s.pop() << endl; // 输出 1
cout << s.empty() << endl; // 输出 1 (true)
```