## 使用队列实现栈 Implement Stack using Queues 原

叶枫啦啦

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.

Notes:

• You must use only standard operations of a queue -- which means only `push to back``peek/pop from front``size`, and `is empty` operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

① 题目要求使用队列实现stack操作。用两个队列q1，q2实现一个栈。push时把新元素添加到q1的队尾。pop时把q1中除最后一个元素外逐个添加到q2中，然后pop掉q1中的最后一个元素，然后注意要保证队列2在使用完成后置为空，以保证我们添加元素时始终向q1中添加。top的道理类似。push: O(1)，pop: O(n)，top: O(n)

class MyStack { //101ms
private Queue<Integer> q1 = new LinkedList<>();
private Queue<Integer> q2 = new LinkedList<>();
/** Initialize your data structure here. */
public MyStack() {}
/** Push element x onto stack. */
public void push(int x) {
q1.offer(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
while(q1.size() > 1) q2.offer(q1.poll());
int top = q1.poll();
Queue tmp = q1;
q1 = q2;
q2 = tmp;
}
/** Get the top element. */
public int top() {
while(q1.size() > 1) q2.offer(q1.poll());
int top = q1.peek();
q2.offer(q1.poll());
Queue tmp = q1;
q1 = q2;
q2 = tmp;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return q1.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/

class MyStack { // 86ms
private Queue<Integer> q1 = new LinkedList<>();
private Queue<Integer> q2 = new LinkedList<>();
/** Initialize your data structure here. */
public MyStack() {}
/** Push element x onto stack. */
public void push(int x) {
q2.offer(x);
while(q1.size() > 0) q2.offer(q1.poll());
Queue tmp = q1;
q1 = q2;
q2 = tmp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return q1.poll();
}
/** Get the top element. */
public int top() {
return q1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return q1.isEmpty();
}
}

③ 只使用一个队列。push时直接添加到队尾就好。pop和top时，把队列除最后一个元素外，逐个循环添加到队列的尾部。push: O(1)，pop: O(n)，top: O(n)

class MyStack { //90ms
private Queue<Integer> q = new LinkedList<>();
/** Initialize your data structure here. */
//public MyStack() {}
/** Push element x onto stack. */
public void push(int x) {
q.offer(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
for (int i = 1;i < q.size() ;i ++ ) {
q.offer(q.poll());
}
return q.poll();
}
/** Get the top element. */
public int top() {
for (int i = 1;i < q.size() ;i ++ ) {
q.offer(q.poll());
}
int top = q.peek();
q.offer(q.poll());
}
/** Returns whether the stack is empty. */
public boolean empty() {
return q.isEmpty();
}
}

### 叶枫啦啦

2016/12/28
2
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

2018/09/04
0
0
LeetCode 225 Implement Stack using Queues（用队列来实现栈）（*）

nomasp
2016/01/20
0
0
LeetCode算法题-Implement Stack Using Queues

2018/12/06
0
0

2011/05/12
16
0

spring mvc主流程源码阅读（剖析）

13分钟前
0
0
vmstat命令详解

https://www.cnblogs.com/ggjucheng/archive/2012/01/05/2312625.html

48分钟前
1
0

yky20190625

5
0

9
0
GitLab Docker 安装记录

0
0