AcWing 20. 用两个栈实现队列
原题链接
简单
作者:
西加加
,
2024-03-25 10:47:07
,
所有人可见
,
阅读 4
Intuition: 首先肯定是要两个stack互相倒的,y总的思路略显麻烦,我的思路是用第一个stacka
存储所有没”处理”的数据,即,所有新数据都push到这里;当a的数据全部倒到b中,只需对b进行pop就可以得到queue的顺序;但当b中有数据时,再对其进行push会破坏先后顺序。
因此做法是新数据全部push到a,需要读取时,如果b有数据则直接对b进行pop/peek,否则就先把a的数据倒过去;这样省去了反复倒的步骤;
class MyQueue {
private:
stack<int> a, b;
public:
/** Initialize your data structure here. */
MyQueue() {
}
void check() {
if (b.size()) return;
while (a.size()) {
b.push(a.top());
a.pop();
}
}
/** Push element x to the back of queue. */
void push(int x) {
a.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
check();
int ret = b.top();
b.pop();
return ret;
}
/** Get the front element. */
int peek() {
check();
return b.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return a.empty() and b.empty();
}
};