序
本文次要记录一下 leetcode 栈之用队列实现栈
题目
应用队列实现栈的下列操作:push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
留神:
你只能应用队列的基本操作 -- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是非法的。你所应用的语言兴许不反对队列。你能够应用 list 或者 deque(双端队列)来模仿一个队列 , 只有是规范的队列操作即可。你能够假如所有操作都是无效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。起源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/implement-stack-using-queues
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
题解
class MyStack {
private Queue<Integer> a;
private Queue<Integer> b;
/** Initialize your data structure here. */
public MyStack() {a = new LinkedList<>();
b = new LinkedList<>();}
/** Push element x onto stack. */
public void push(int x) {a.offer(x);
// 将 b 队列中元素全副转给 a 队列
while(!b.isEmpty())
a.offer(b.poll());
// 替换 a 和 b, 使得 a 队列没有在 push() 的时候始终为空队列
Queue temp = a;
a = b;
b = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {return b.poll();
}
/** Get the top element. */
public int top() {return b.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {return b.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();
*/
小结
这里应用了两个 LinkedList,在 push 的时候,offer 到 a 队列,而后再将 b 队列的元素 offer 到 a 队列,再替换 a、b 队列;pop、top、empty 的时候间接操作 b 队列。
doc
- 用队列实现栈