/
QueueUsingTwoStacks.java
105 lines (72 loc) · 1.9 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
package playground.dsa.queueUsingTwoStacks;
import playground.dsa.stack.Stack;
import playground.dsa.stack.StackOverflowException;
import playground.dsa.stack.StackUnderflowException;
/**
* A queue of ints that uses all n storage elements for queue element storage.
*/
public class QueueUsingTwoStacks implements Queue {
private Stack active;
private Stack aux;
private Order order;
public QueueUsingTwoStacks(int capacity) {
this.active = new Stack(capacity);
this.aux = new Stack(capacity);
this.order = Order.LIFO;
}
@Override
public void enqueue(int i) throws QueueOverflowException {
if (Order.FIFO.equals(order)) {
flip();
}
try {
active.push(i);
}
catch(StackOverflowException e) {
throw new QueueOverflowException();
}
}
@Override
public int dequeue() throws QueueUnderflowException {
if (Order.LIFO.equals(order)) {
flip();
}
try {
return active.pop();
}
catch(StackUnderflowException e) {
throw new QueueUnderflowException();
}
}
@Override
public boolean isEmpty() {
return active.isEmpty();
}
@Override
public boolean isFull() {
return active.isFull();
}
@Override
public String dump() {
return "NOT IMPLEMENTED";
}
private void flip() {
try {
while (!active.isEmpty()) {
aux.push(active.pop());
}
if (Order.FIFO.equals(order)) {
order = Order.LIFO;
}
else {
order = Order.FIFO;
}
Stack tmp = active;
active = aux;
aux = tmp;
}
catch (Exception e) {
throw new IllegalStateException(e);
}
}
}