描述
Implement the following operations of a stack using queues.
- push(x) – Push element x onto stack.
- pop() – Removes the element on top of the stack.
- top() – Get the top element.
- empty() – Return whether the stack is empty.
分析
用队列实现堆栈,与leetcode-232-Implement-Queue-using-Stacks相关联。队列的特点是先进先出,所以入队的元素总是在队尾,出队的元素总是在队首,而堆栈的特点是后进先出,要实现这一点,我们可以让后面进的元素排在队首。如何实现呢,用两个队列实现,一个队列始终是空的,当入队时,元素进空的队列,另一个队列的所有元素排在它的后面(实现插队)。出栈操作,即让有元素的队列出队即可,判断栈空,两个队列都为空即为栈空。
解决方案(C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| class Stack { public: void push(int x) { if(q1.empty()) { q1.push(x); while(!q2.empty()){ int temp = q2.front(); q2.pop(); q1.push(temp); } }else { q2.push(x); while(!q1.empty()) { int temp = q1.front(); q1.pop(); q2.push(temp); } } }
void pop() { if (!q1.empty()){ q1.pop(); } if (!q2.empty()) { q2.pop(); } }
int top() { if(!q1.empty()) { return q1.front(); } if(!q2.empty()) { return q2.front(); } }
bool empty() { return q1.empty() && q2.empty(); } private: queue<int> q1, q2; };
|
相关问题