CC-6 : Implement Queue using 2 Stacks.
Description:
A Stack data structure follows Last In, First Out (LIFO) principle. Implement a FIFO Queue using 2 stacks.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
QueueUsingStacks queue=new QueueUsingStacks();
queue.add(9);
queue.add(14);
queue.add(17);
queue.add(34);
queue.add(21);
queue.add(28);
|
Queue nodes: 9 <- 14 <- 17 <- 34 <- 21 <- 28
|
queue.remove();
queue.remove();
queue.add(44);
queue.add(55);
|
Queue nodes:17 <- 34 <- 21 <- 28<-44<-55
|
Pseudocode:
| Declare and initialize 2 stacks by name of stk and Q.
|
| Whenever a new element is to be added to FIFO Queue, add it to stk.
|
| Whenever an element needs to be removed from FIFO Queue:
Pop elements one by one from stk and push to Q till stk becomes empty.
Return first element from Q.
|
Code:
public class QueueUsingStacks {
private Stack<Integer> stk=new Stack<Integer>();
private Stack<Integer> Q=new Stack<Integer>();
public boolean add(int data){
stk.push(data);
return true;
}
public int remove() {
if (Q.size()==0) {
while (stk.size()!=0) {
Q.push(stk.pop());
}
}
return Q.pop();
}
public int get() {
if (Q.size()==0) {
while (stk.size()!=0) {
Q.push(stk.pop());
}
}
return Q.peek();
}
public int getSize() {
return Q.size()+stk.size();
}
}
Click here to download and run code and test cases !
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Stack;
public class QueueUsingStacks {
private Stack<Integer> stk=new Stack<Integer>();
private Stack<Integer> Q=new Stack<Integer>();
public boolean add(int data){
stk.push(data);
return true;
}
public int remove() {
if (Q.size()==0) {
while (stk.size()!=0) {
Q.push(stk.pop());
}
}
return Q.pop();
}
public int get() {
if (Q.size()==0) {
while (stk.size()!=0) {
Q.push(stk.pop());
}
}
return Q.peek();
}
public int getSize() {
return Q.size()+stk.size();
}
public void printQueue() throws Exception {
if ((Q.size() == 0)&&(stk.size()==0)) { System.out.println("Queue empty"); return; }
System.out.println();
System.out.println("*********************************************************************");
System.out.print("Queue nodes: ");
ListIterator lsitr=Q.listIterator(Q.size());
while (lsitr.hasPrevious()) {
System.out.print(lsitr.previous());
System.out.print(" <- ");
}
Iterator itr=stk.iterator();
while (itr.hasNext()) {
System.out.print(itr.next());
System.out.print(" <- ");
}
System.out.println();
System.out.println("*********************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
public static void main(String[] args) {
/* Test cases given below: */
try {
QueueUsingStacks queue=new QueueUsingStacks();
System.out.print("Add to Queue");
queue.add(9);
queue.printQueue();
System.out.print("Add to Queue");
queue.add(14);
queue.printQueue();
System.out.print("Add to Queue");
queue.add(17);
queue.printQueue();
System.out.print("Add to Queue");
queue.add(34);
queue.printQueue();
System.out.print("Add to Queue");
queue.add(21);
queue.printQueue();
System.out.print("Add to Queue");
queue.add(28);
queue.printQueue();
System.out.println("QUEUE SIZE "+queue.getSize());
System.out.print("\nRemove from Queue");
queue.remove();
queue.printQueue();
System.out.print("Remove from Queue");
queue.remove();
queue.printQueue();
System.out.print("Add to Queue");
queue.add(44);
queue.printQueue();
System.out.print("Add to Queue");
queue.add(55);
queue.printQueue();
System.out.print("Remove from Queue");
System.out.println("GET FIRST NODE "+queue.get());
queue.remove();
queue.printQueue();
System.out.print("\nRemove from Queue");
queue.remove();
queue.printQueue();
System.out.print("Remove from Queue");
queue.remove();
queue.printQueue();
System.out.print("Remove from Queue");
queue.remove();
queue.printQueue();
System.out.println("QUEUE SIZE "+queue.getSize());
System.out.println("\nGET FIRST NODE "+queue.get());
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
}
}
}