-
-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathImplement Queue using Stacks.java
More file actions
executable file
·197 lines (163 loc) · 5.77 KB
/
Copy pathImplement Queue using Stacks.java
File metadata and controls
executable file
·197 lines (163 loc) · 5.77 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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
E
1520797719
tags: Stack, Design
#### 双Stack
画图, 知道最后maintain的stack是那个 reverseStack: pop(), peek(), empty() 都在这个stack上, 无需变换.
push()里面做stack和reverseStack的来回倾倒.
相比老的code, 在PUSH里面做倾倒, 更容易读.
#### Previous notes
双Stack. 一个是等于是queue，一个是backfillStack.
Tricky: 是在pop()和peek()的时候backfill, 并且要等到stack用完再backfill.
写一下例子就知道，如果提早backfill，stack.peek()就不是queue的head了.
```
/*
LeetCode:
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).
*/
/*
Thoughts:
Use 2 stacks:
Stack: hold items in regular stack order
ReverseStack: hold items in the queue order.
- Add: pure from reverseStack into stack, add item, and pure back into reverseStack.
- Remove: remove from reverseStack
- peek, empty are trivial
*/
class MyQueue {
Stack<Integer> stack;
Stack<Integer> reverseStack;
/** Initialize your data structure here. */
public MyQueue() {
stack = new Stack<>();
reverseStack = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
while (!reverseStack.isEmpty()) {
stack.push(pop());
}
stack.push(x);
// Pure back
while (!stack.isEmpty()) {
reverseStack.push(stack.pop());
}
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
return reverseStack.pop();
}
/** Get the front element. */
public int peek() {
return reverseStack.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return reverseStack.isEmpty();
}
}
/*
Thoughts:
Using two stack.
Stack1 holds the correct representation of the queue: first added item appears on top of stack.
Stack2 used to insert new item, which will be like a inverse queue.
Note: Only backfill stack2 into stack1, when stack1.isEmpty() during queue.pop/queue.peek: only backfilling when regular queue is drained.
*/
class MyQueue {
private Stack<Integer> stack;
private Stack<Integer> backfillStack;
/** Initialize your data structure here. */
public MyQueue() {
stack = new Stack<>();
backfillStack = new Stack<>();
}
private void backfill() {
while (!backfillStack.isEmpty()) {
stack.push(backfillStack.pop());
}
}
/** Push element x to the back of queue. */
public void push(int x) {
backfillStack.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (stack.isEmpty()) {
backfill();
}
return stack.pop();
}
/** Get the front element. */
public int peek() {
if (stack.isEmpty()) {
backfill();
}
return stack.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stack.isEmpty() && backfillStack.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
/*
LintCode: Implement Queue by Two Stacks
As the title described, you should only use two stacks to implement a queue's actions.
The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.
Both pop and top methods should return the value of first element.
Example
For push(1), pop(), push(2), push(3), top(), pop(), you should return 1, 2 and 2
Challenge
implement it by two stacks, do not use any other data structure and push, pop and top should be O(1) by AVERAGE.
Thoughts:
1. Push everything into stack2: whatever comes in last, will be on top.
2. Pop and Top: return stack1's top element.
3. Initially, when stack1 is empty, need to reverse all stack2 and put into stack: like pouring water from cup stack2 into cup stack1.
Or:when stack1 has been top() over, pour stack2 into stack1 again: the stack2's bottom becomes stack1's top, which is correct: returning the oldest element of queue (front of queue)
Tags Expand
LintCode Copyright Stack Queue
*/
public class Solution {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public void pourS2ToS1(){
while (!stack2.empty()) {
stack1.push(stack2.peek());
stack2.pop();
}
}
public Solution() {
stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();
}
public void push(int element) {
stack2.push(element);
}
public int pop() {
if (stack1.empty()) {
pourS2ToS1();
}
return stack1.pop();
}
public int top() {
if (stack1.empty()) {
pourS2ToS1();
}
return stack1.peek();
}
}
```