- Notifications
You must be signed in to change notification settings - Fork 19.9k
/
Copy pathQueueUsingTwoStacks.java
105 lines (95 loc) · 2.57 KB
/
QueueUsingTwoStacks.java
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
packagecom.thealgorithms.others;
importjava.util.Stack;
/**
* This implements Queue using two Stacks.
*
* <p>
* Big O Runtime: insert(): O(1) remove(): O(1) amortized isEmpty(): O(1)
*
* <p>
* A queue data structure functions the same as a real world queue. The elements
* that are added first are the first to be removed. New elements are added to
* the back/rear of the queue.
*
* @author sahilb2 (https://www.github.com/sahilb2)
*/
publicclassQueueUsingTwoStacks {
privatefinalStack<Object> inStack;
privatefinalStack<Object> outStack;
/**
* Constructor
*/
publicQueueUsingTwoStacks() {
this.inStack = newStack<>();
this.outStack = newStack<>();
}
/**
* Inserts an element at the rear of the queue
*
* @param x element to be added
*/
publicvoidinsert(Objectx) {
// Insert element into inStack
this.inStack.push(x);
}
/**
* Remove an element from the front of the queue
*
* @return the new front of the queue
*/
publicObjectremove() {
if (this.outStack.isEmpty()) {
// Move all elements from inStack to outStack (preserving the order)
while (!this.inStack.isEmpty()) {
this.outStack.push(this.inStack.pop());
}
}
returnthis.outStack.pop();
}
/**
* Peek at the element from the front of the queue
*
* @return the front element of the queue
*/
publicObjectpeekFront() {
if (this.outStack.isEmpty()) {
// Move all elements from inStack to outStack (preserving the order)
while (!this.inStack.isEmpty()) {
this.outStack.push(this.inStack.pop());
}
}
returnthis.outStack.peek();
}
/**
* Peek at the element from the back of the queue
*
* @return the back element of the queue
*/
publicObjectpeekBack() {
returnthis.inStack.peek();
}
/**
* Returns true if the queue is empty
*
* @return true if the queue is empty
*/
publicbooleanisEmpty() {
return (this.inStack.isEmpty() && this.outStack.isEmpty());
}
/**
* Returns true if the inStack is empty.
*
* @return true if the inStack is empty.
*/
publicbooleanisInStackEmpty() {
return (inStack.isEmpty());
}
/**
* Returns true if the outStack is empty.
*
* @return true if the outStack is empty.
*/
publicbooleanisOutStackEmpty() {
return (outStack.isEmpty());
}
}