forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMyQueue.java
More file actions
102 lines (95 loc) · 2.89 KB
/
MyQueue.java
File metadata and controls
102 lines (95 loc) · 2.89 KB
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// Source : https://leetcode.com/problems/implement-queue-using-stacks/description/
// Author : Tianming Cao
// Date : 2018-02-02
/**********************************************************************************
* Implement the following operations of a queue using stacks.
*
* push(x) -- Push element x to the back of queue.
* pop() -- Removes the element from in front of queue.
* peek() -- Get the front element.
* empty() -- Return whether the queue is empty.
*
* Notes:
* You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
* Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
* You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
*
**********************************************************************************/
package myQueue;
import java.util.Stack;
/**
* This problem is a sibling of problem 225(https://leetcode.com/problems/implement-stack-using-queues/description/)
* The solution is:
* 1. stack1 is always in charge of push operation
* 2. stack2 is always in charge of peek and pop operation
* 3. if we want to do peek or pop operation, but stack2 is empty,
* we should first pop all the elements from stack1 and push them into stack2 in turn.
* Give a Example:
*
* First, push numbers "1,2,3,4,5" to stack1, then stack1's structure is:
*
* |5|
* |4|
* |3|
* |2|
* |1|
*
* Second, if we want to get the front element "1",we should pop all the elements of stack1 and push them into stack2,
* after this, stack1 is empty, and stack2's structrue is:
*
* |1|
* |2|
* |3|
* |4|
* |5|
*
* So we can get stack2's top element "1" as the front element of queue.
*
* Next, if we want to push "6" to the back of queue, we should push "6" into stack1 as before, so stack1's structure is:
*
* |6|
*
* Finally, if we want to do pop operation twice ,we should remove the top element of stack2 twice, so stack2's structure is:
*
* |3|
* |4|
* |5|
*
* as expect, the removed element is "1" and "2".
*/
public class MyQueue {
public Stack<Integer> stack1;
public Stack<Integer> stack2;
public int size;
public MyQueue() {
stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();
size = 0;
}
public void push(int x) {
stack1.push(x);
size++;
}
public int pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
int value = stack2.pop();
size--;
return value;
}
public int peek() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
int value = stack2.peek();
return value;
}
public boolean empty() {
return size == 0 ? true : false;
}
}