In one of the interviews I was asked to design and code a queue out of two stacks.
Design
Thinking over this, one thing immediately comes in mind, why 2 stacks are given, why can't just one.
Second thing, which is a little obvious that stack is LIFO while queue is FIFO so there is some way to design FIFO behavior given 2 stacks.
Though I was thinking in a different way and was trying to connect two stacks and having pointers/links to the beginning and at the end of the connected stacks. Data can be added to the stack just like in array or array list, and when data need to removed, it can use the beginning pointer and remove it from the collection and at the same time shift all the remaining elements one position forward (i.e towards the begining of the list). I think this solution isn't really convincing in the sense that it isn't answering, why the 2nd stack needed.
So one of the right approaches (or the only right approach ?) which justifies the need of the 2nd stack, is to use 2nd stack as an intermediary storage while simulating queue from the 1st stack.
Make it simple...
1) To ADD() data to the queue, just delegate call to PUSH() in the 1st stack. But when data needs to be removed from the queue, it has to follow FIFO style (unlike LIFO). It means the fist element from the 1st stack needs to be removed. Since there is only one pointer (i.e. stack pointer) for a stack, which always points to the location of the next element to be added (i.e. last element added + 1), so it would not be pointing to the first element (until stack has got just one element).
2) It essentially means that before performing remove operation on the queue, all the remaining data (except data at 0th location) from the 1st stack has to be POPED() and moved into the 2nd stack. Then stack pointer reaches to the first element and can be POPED and REMOVED.
3) Then the remaining elements (from the 2nd stack) can be PUSHED back to the 1st stack.
4) And cycle contunues this way depending on how may elements to be added/removed
Code
Here is the code:
-----------------
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
public class QueueFromStacks {
private Stack st1;
private Stack st2;
public QueueFromStacks() {
st1 = new Stack();
st2 = new Stack();
}
public static class Stack {
private List elements = null;
private int pointer;
public Stack() {
pointer = 0;
elements = new ArrayList();
}
public void push(String str) {
if(pointer <= elements.size()) {
elements.add(pointer, str);
pointer++;
}
//System.out.println(pointer);
}
public String pop() {
String tmpStr = "";
pointer--;
if(pointer >= 0) tmpStr = elements.remove(pointer);
else tmpStr = "null";
return tmpStr;
}
}
public static void main(String[] args) {
QueueFromStacks q = new QueueFromStacks();
for(int i = 0; i < 20; i++) {
q.add("a" + i);
}
System.out.println("Original Stack behaves like queue->before removing element: " + q.toString());
q.remove();
System.out.println("Original Stack behaves like queue->after removing element: " + q.toString());
}
public String toString() {
String tmp = "";
Iterator it = this.st1.elements.iterator();
while(it.hasNext()) {
tmp += it.next() + ", ";
}
return tmp;
}
public void add(String str) {
st1.push(str);
}
public void remove() {
//pop from 1st and push into 2nd
int tmpCounter = st1.elements.size() - 1;
while(tmpCounter != 0) {
st2.push(st1.pop());
tmpCounter--;
}
if(tmpCounter == 0) {
String tmpPop = st1.pop();
System.out.println("First element removed from the queue: " + tmpPop);
}
//now push back into the 1st one from 2nd
int tmpCounter1 = st2.elements.size() - 1;
while(tmpCounter1 >= 0) {
st1.push(st2.pop());
tmpCounter1--;
}
}
}
-----------------
Wrapping Up
I would be happy to hear from you. It may have other better solutions/code, please share if you have one.
Until next time,
Sanjay Semwal
