Implement queue using stacks

Implement queue using stacks

Before implementing queue using stacks, let’s understand what is queue and stack as abstract data structures. We already know that stack is a LIFO data structure, i.e. what goes in last, comes out first. Contrary to that, queue is a FIFO data structure, where what goes in first comes out first. Read array based queue implementation and linked list based queue and stack implementation for detailed discussions.

Implement queue using stacks

Ask of the problem is to implement a FIFO data structure using LIFO data structure. Insertion in LIFO or FIFO data structure should not be a problem. As insertion in stack (LIFO) or queue (FIFO) does not vary. Removal or dequeuing items from LIFO and FIFO is totally different. Let’s take an example, with following elements to be queued and dequeued from queue : 1,2,3,4,6,7,8. Start implement queue with one stack S. Insert 1, S = {1}. No problem, even queue would have behaved in same way.
Insert 2 will result in S = {1,2}. No problem again.
Insert 3 will result in S = {1,2,3}.

Here comes tricky part. Dequeue now from stack. As per the definition of queue, first item, 1 in this case, should come out. However, we have stack with us, we can pop 3 from top of stack. So what to do now?
Simple, pop all elements from stack and take last element in stack. Cool!
What happens to all elements just popped out of stack? They are lost now. How can we save them too while popping elements from stack. While popping out elements from S, put popped elements into another stack. 

After this, top of stack S2 will gives element entered in first stack after the element just dequeue, in this case 1. Now stacks are S = {} and S2 = {3,2}.
What if we insert 4. Where should it go or which stack it should be pushed into?
As explained, stack 2 contains elements in FIFO order (because we pushed element in reverse order of the first stack). Do not change S2 till it is empty. Hence,candidate for holding 4 is first stack S. S = {4}, S2 = {3,2}
Dequeue 2. Easy return top of the stack. S ={4} S2 ={3}
Dequeue 3. Easy return top of the stack. S ={4} S2 {}
Now Insert 5, simple add it to S. S ={4,5} S2 = {}
Dequeue. Pop all elements from the S and put them into S2. Now pop from S2 and return the element. Continue till we have operations to perform.

Queue using stack implementation

#include <stdio.h>
#define STACK_SIZE 10
 
typedef struct stack{
        int top;
        int items[STACK_SIZE];
}stack;
 
void initializeStack(stack *s){
	s->top = -1;
}
void push(stack *ms, int element){
   if(ms->top < STACK_SIZE-1){
       ms->items[++(ms->top)] = element;
   }
   else {
       printf("Stack is full\n");
   }
}
 
int pop (stack *ms){
   if(ms->top >= 0){
       return ms->items[(ms->top)--];
   } 
   else{
       printf("Stack is empty\n");
   }
}

int peek(stack ms){
  if(ms.top<0){
      printf("Stack empty\n");
      return 0;
   }
   return ms.items[ms.top];
}

int isEmpty(stack *ms){
   if(ms->top <0) return 1;
   else return 0;
}

void implementQueueUsingStacks(int choice, stack *s1, 
                               stack *s2, int n){
        
    switch(choice){
        case 1: //enqueue
            push(s1,n);
            break;

        case 2 : //dequeue
            if(!isEmpty(s2)){
                printf("\n Element dequeued is : %d", pop(s2));
            }
            else{
                while(!isEmpty(s1)){
                    push(s2, pop(s1));
                }
                printf("\n Element dequeued is : %d", pop(s2));
            }
            break;
      }
}

int main(void) {
	stack s1, s2;
	initializeStack(&s1);
	initializeStack(&s2);
	for(int i=0; i<10; i++){
		implementQueueUsingStacks(i%3, &s1, &s2,i);
	}
	return 0;
}

Only an auxiliary space is required for extra stack. Insertion is O(1). Dequeue operation in worst case can be O(N).

Please share if there is something wrong or missing. If you are interested in contributing to algorithms and me or have an interview experience to share, please contact us.