forked from anitaa1990/Android-Cheat-sheet
- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQueuesUsingStack.java
More file actions
Latest commit
134 lines (104 loc) · 4.59 KB
/
Copy pathQueuesUsingStack.java
File metadata and controls
134 lines (104 loc) · 4.59 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
packagequeue;
importjava.util.Stack;
publicclassQueuesUsingStack {
/*
* Implement a queue using stack.
* */
/*
* A stack is a data structure in which objects are inserted and removed according to the LIFO(Last In First Out)
* principle. An item is added at the top of the stack and removed from the top as well. push means to insert an item
* at the top of the stack and pop means to remove an item from the top of the stack.
*
* A queue is a data structure in which objects are inserted and removed according to the FIFO(First In First Out)
* principle. An item is added at the back of the queue and removed from the front. enqueue means to insert an item
* at the back of the queue and dequeue means to remove an item from the front of the queue.
*
* Runtime Complexity
* enqueue(): Constant, O(1).
* dequeue(): Linear, O(n).
* Memory Complexity - Linear, O(n).
* */
publicstaticvoidmain(String[] args) throwsException {
QueueUsingStackWithFasterEnqueuequeueUsingStackWithFasterEnqueue = newQueueUsingStackWithFasterEnqueue();
queueUsingStackWithFasterEnqueue.enqueue(3);
queueUsingStackWithFasterEnqueue.enqueue(6);
queueUsingStackWithFasterEnqueue.enqueue(10);
queueUsingStackWithFasterEnqueue.dequeue();
System.out.println(queueUsingStackWithFasterEnqueue.stack1 + "###" + queueUsingStackWithFasterEnqueue.stack2);
queueUsingStackWithFasterEnqueue.enqueue(8);
queueUsingStackWithFasterEnqueue.enqueue(4);
queueUsingStackWithFasterEnqueue.dequeue();
System.out.println(queueUsingStackWithFasterEnqueue.stack1 + "###" + queueUsingStackWithFasterEnqueue.stack2);
/* Faster Dequeue */
QueueUsingStackWithFasterDequeuequeueUsingStackWithFasterDequeue = newQueueUsingStackWithFasterDequeue();
queueUsingStackWithFasterDequeue.enqueue(3); //q1 = 3
queueUsingStackWithFasterDequeue.enqueue(6); //q1 = 6,3
queueUsingStackWithFasterDequeue.enqueue(10); //q1 = 10,6,3
System.out.println(queueUsingStackWithFasterDequeue.dequeue()); //q1 = 10,6 3 is removed
System.out.println(queueUsingStackWithFasterDequeue.stack1 + "###" + queueUsingStackWithFasterDequeue.stack2);
queueUsingStackWithFasterDequeue.enqueue(8); //q1 = 8,10,6
queueUsingStackWithFasterDequeue.enqueue(4); //q1 = 4, 8,10,6
System.out.println(queueUsingStackWithFasterDequeue.dequeue()); //q1 = 4,8,10 6 is removed
System.out.println(queueUsingStackWithFasterDequeue.stack1 + "###" + queueUsingStackWithFasterDequeue.stack2);
}
}
/*
* enqueue(): Always push on stack1
* dequeue():
* If queue size is 0, throw exception.
* If stack2 has element(s), pop the topmost and return.
* Otherwise If stack1 is non empty, pop all elements from stack1 and push them in stack2.
* At the end pop stack2's top most element and return.
* */
classQueueUsingStackWithFasterEnqueue {
Stack<Integer> stack1 = newStack<>();
Stack<Integer> stack2 = newStack<>();
publicvoidenqueue(intdata) {
stack1.push(data);
}
publicbooleanisEmpty() {
returnstack1.size() + stack2.size() == 0;
}
publicintdequeue() throwsException {
if(isEmpty()) {
thrownewException("Queue is empty!");
}
if(stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
returnstack2.pop();
}
}
/*
* enqueue():
* Pop each element from stack1 and push it to stack2.
* Push item being enqueued to stack1.
* Pop each element back from stack2 and push it to stack1.
* dequeue():
* If queue size is 0, throw exception.
* Pop from stack1 and return.
* */
classQueueUsingStackWithFasterDequeue {
Stack<Integer> stack1 = newStack<>();
Stack<Integer> stack2 = newStack<>();
publicbooleanisEmpty() {
returnstack1.size() + stack2.size() == 0;
}
publicvoidenqueue(intdata) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
stack1.push(data);
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
}
publicintdequeue() throwsException {
if(isEmpty()) {
thrownewException("Stack is empty!");
}
returnstack1.pop();
}
}