https://leetcode.com/problems/implement-stack-using-queues/description/
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).
第一个做法：复杂，啰嗦，受到 impelement queue using two stacks 的影响 queue 和 stack 不一样，倒腾多次并不会发生结构的变化
1 public class LC_225_ImplementStackUsingTwoQueues_I {
2
3 private Queue<Integer> queue1;
4 private Queue<Integer> queue2;
5
6 public LC_225_ImplementStackUsingTwoQueues_I() {
7 queue1 = new LinkedList<>();
8 queue2 = new LinkedList<>();
9 }
10
11 /**
12 * Push element x onto stack.
13 */
14 public void push(int x) {
15 if (!queue1.isEmpty()) {
16 queue1.offer(x);
17 } else {
18 queue2.offer(x);
19 }
20 }
21
22 /**
23 * Removes the element on top of the stack and returns that element.
24 */
25 public int pop() {
26 if (!queue1.isEmpty() && queue2.isEmpty()) {
27 int size = queue1.size();
28 shuffle(queue1, queue2, size - 1);
29 return queue1.poll();
30 } else {
31 int size = queue2.size();
32 shuffle(queue2, queue1, size - 1);
33 return queue2.poll();
34 }
35 }
36
37 /**
38 * Get the top element.: peek
39 */
40 public int top() {
41 int value = 0;
42 if (!queue1.isEmpty() && queue2.isEmpty()) {
43 int size = queue1.size();
44 shuffle(queue1, queue2, size - 1);
45 value = queue1.poll();
46 queue2.offer(value);
47 } else {
48 int size = queue2.size();
49 shuffle(queue2, queue1, size - 1);
50 value = queue2.poll();
51 queue1.offer(value);
52 }
53 return value;
54 }
55
56 //make sure queue1 and queue2 only one has values
57 private void shuffle(Queue<Integer> from, Queue<Integer> to, int times) {
58 for (int i = 0; i < times; i++) {
59 to.offer(from.poll());
60 }
61 }
62
63 /**
64 * Returns whether the stack is empty.
65 */
66 public boolean empty() {
67 return queue1.isEmpty() && queue2.isEmpty();
68 }
69 }
方法2: 换指针，queue1 永远都是 非空， 倒腾到 queue2 中后，改变 reference 就行。注意这里 cut reference 的好习惯
1 public class LC_225_ImplementStackUsingTwoQueues_II {
2
3 private Queue<Integer> queue1;
4 private Queue<Integer> queue2;
5
6 public LC_225_ImplementStackUsingTwoQueues_II() {
7 queue1 = new LinkedList<>();
8 queue2 = new LinkedList<>();
9 }
10
11 /**
12 * Push element x onto stack.
13 */
14 public void push(int x) {
15 queue1.offer(x);
16 }
17
18 /**
19 * Removes the element on top of the stack and returns that element.
20 */
21 public int pop() {
22 int size = queue1.size();
23 shuffle(queue1, queue2, size - 1);
24 int value = queue1.poll();
25 //cut the reference
26 queue1 = new LinkedList<>(queue2) ;
27 queue2.clear();
28 return value ;
29 }
30
31 /**
32 * Get the top element.: peek
33 */
34 public int top() {
35 int value = 0;
36 int size = queue1.size();
37 shuffle(queue1, queue2, size - 1);
38 value = queue1.poll();
39 queue2.offer(value);
40 //cut the reference
41 queue1 = new LinkedList<>(queue2) ;
42 queue2.clear();
43 return value;
44 }
45
46 //make sure queue1 and queue2 only one has values
47 private void shuffle(Queue<Integer> from, Queue<Integer> to, int times) {
48 for (int i = 0; i < times; i++) {
49 to.offer(from.poll());
50 }
51 }
52
53 /**
54 * Returns whether the stack is empty.
55 */
56 public boolean empty() {
57 return queue1.isEmpty() && queue2.isEmpty();
58 }
59 }