Stack implementation using two Queues
Push :
- To push elements in Stack we are using two Queues q1 and q2.
- q1 is using as main queue.
- q2 is using as temporary queue.
- If queue1 is empty, add elements to q1
- If q1 is not empty, than first add (shift) all elements from q1 to q2, add new element (current element) to q1 and copy(re-add) all elements from q2 to q1.
Pop :
- q1 will be use to pop elements from stack (simply remove element from q1)
Lets understand by below image.
Code:
package com.javaiq.in;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
public class StackImplUsingTwoQueues {
Queue<Integer> q1;
Queue<Integer> q2;
StackImplUsingTwoQueues() {
q1 = new LinkedList<Integer>();
q2 = new LinkedList<Integer>();
}
/*
* Before add new element in q1, q1 must be empty,
* if q1 is not empty then shift all element of q1 to q2,
* after adding new element in q1, re-add all element from q2 to q1
*/
public void push(int i) {
if (q1.size() == 0) {
/* As q1 is empty so add new element into q1 */
q1.add(i);
} else {
int sizeOfQueue1 = q1.size();
// Copy or shift all elements from q1 to q2
for (int j = 0; j < sizeOfQueue1; j++) {
q2.add(q1.remove());
}
/* Add new element */
q1.add(i);
// Copy or re-add elements from q2 to q1
for (int k = 0; k < sizeOfQueue1; k++) {
q1.add(q2.remove());
}
}
}
public int pop() {
if (q1.size() == 0)
throw new NoSuchElementException("Underflow Exception");
return q1.remove();
}
}
Test Program:
public static void main(String[] args) {
StackImplUsingTwoQueues stack = new StackImplUsingTwoQueues();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(10);
stack.push(11);
System.out.println("Removed element from stack : " + stack.pop());
stack.push(15);
System.out.println("Removed element from stack : " + stack.pop());
}
Output:
Removed element from stack : 11
Removed element from stack : 15
As per the output we can see last pused element is 15, and pop element is
15.
Related Tutorial
No comments:
Post a Comment