LeetCode--Implement Stack using Queues

本文主要是介绍LeetCode--Implement Stack using Queues，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem:

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.

Analysis:

【解法一：用两个队列，push: O(1)，pop: O(n)，top: O(n)】
用两个队列q1，q2实现一个栈。push时把新元素添加到q1的队尾。pop时把q1中除最后一个元素外逐个添加到q2中，然后pop掉q1中的最后一个元素，然后注意记得q1和q2，以保证我们添加元素时始终向q1中添加。top的道理类似。

【解法二：用两个队列，push: O(n)，pop: O(1)，top: O(1)】
所有元素都倒序保存在q1中，即后添加的元素在q1的最前端，如何做到呢？每次push时，把新元素放到空的q2，然后把q1中元素逐个添加到q2的队尾，最后交换q1和q2。这样q1队首的元素就是最后添加的元素，pop和top直接返回q1队首的元素就好。

Anwser1:

class MyStack {Queue<Integer> in =  new LinkedList<Integer>();Queue<Integer> out = new LinkedList<Integer>();// Push element x onto stack.public void push(int x) {in.add(x);}// Removes the element on top of the stack.public void pop() {while(in.size()>1) out.add(in.poll());in.poll();Queue<Integer> q=in;in = out;out = q;}// Get the top element.public int top() {while(in.size()>1) out.add(in.poll());int x = in.poll();out.add(x);Queue<Integer> q=in;in = out;out = q;return x;}// Return whether the stack is empty.public boolean empty() {return in.isEmpty();       }
}

Anwser2:

class MyStack {private Queue<Integer> q1 = new LinkedList<>();private Queue<Integer> q2 = new LinkedList<>();// Push element x onto stack.public void push(int x) {q2.offer(x);while (!q1.isEmpty()) {q2.offer(q1.poll());}Queue tmp = q1;q1 = q2;q2 = tmp;}// Removes the element on top of the stack.public void pop() {q1.poll();}// Get the top element.public int top() {return q1.peek();}// Return whether the stack is empty.public boolean empty() {return q1.isEmpty();}
}