A queue is a data structure that follows the First In First Out (FIFO) principle, which means that the first element that is added to the queue will be the first one to be removed. A stack is a data structure that follows the Last In First Out (LIFO) principle, which means that the last element that is added to the stack will be the first one to be removed.
It is possible to implement a queue using a stack by using two stacks. One stack will be used to enqueue elements, and the other stack will be used to dequeue elements.
When an element is added to the queue, it is pushed onto the enqueue stack. When an element is removed from the queue, it is popped from the dequeue stack.
If the dequeue stack is empty, all elements are popped from the enqueue stack and pushed onto the dequeue stack before the element is popped. This allows the queue to maintain the correct order of the elements while using the LIFO structure of the stack to store and retrieve them.
Queue implementation using stack:
1.By making dequeue operation costly
It is possible to implement a queue using a stack by making the dequeue operation more costly than the enqueue operation. This can be done by using two stacks, one for enqueuing elements and one for dequeuing elements.
When an element is added to the queue, it is pushed onto the enqueue stack. When an element is removed from the queue, the dequeue stack is checked to see if it is empty. If the dequeue stack is empty, all elements are popped from the enqueue stack and pushed onto the dequeue stack before the element is popped.
This allows the queue to maintain the correct order of the elements while using the LIFO structure of the stack to store and retrieve them.
Making the dequeue operation more costly in this way has the advantage of reducing the time complexity of the enqueue operation to O(1) in the best case and O(1) in the worst case.
However, it increases the time complexity of the dequeue operation to O(n) in the best case and O(n) in the worst case, where n is the number of elements in the queue. This means that enqueuing elements is very fast, but dequeuing elements becomes slower as the queue grows larger.
The space complexity of this implementation is also O(n), where n is the number of elements in the queue, because both stacks must be able to hold all of the elements in the queue in order to maintain the correct order of the elements.
Implementing queue using stack by making dequeue costly using dynamic array in C
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void main()
{
int *stack1,*stack2,x=0,top1=-1,top2=-1,i,count=0,size,value,
choice;
printf("enter size of arrayn");
scanf("%d",&size);
stack1= malloc(size*sizeof(int));
stack1= malloc(size*sizeof(int));
while(x<1)
{
printf("n 1.ENQUEUE");
printf("n 2.DEQUEUE");
printf("n 3.DISPLAY");
printf("n 4.EXIT ");
printf("n ENTER YOUR CHOICE n");
scanf(" %d",&choice);
switch (choice)
{
case 1:
if(top1==size-1)
{
printf("overflown");
break;
}
else
{
printf("enter the value");
scanf("%d",&value);
printf("nCurrent stack1 top1 value=%d",top1);
top1=top1+1;
printf("nstack1 top1 become=%d",top1);
stack1[top1]=value;
count=count+1;
printf("nValue enqueue successfully");
}
break;
case 2:
if(top1==-1)
{
printf("underflown");
break;
}
else
{
printf("stack1 current top1 value=%d n",top1);
printf("starting dequeuen");
for(i=0;i<count;i++)
{
top2=top2+1;
printf("copy top1=%d to stack2n",top1);
stack2[top2]=stack1[top1];
top1=top1-1;
}
printf("stack 1 is copyied to stack 2 successfullyn");
stack2[top2--];
count=count-1;
printf("first item of stack1 or top item of stack2 is poped");
printf("nAgain copying stack 2 to stack 1");
printf("ncurrent value of stack1 top1 =%d n",top1);
for(i=0;i<count;i++)
{
top1=top1+1;
printf("nstack1 top1 value become=%d n",top1);
stack1[top1]=stack2[top2];
top2=top2-1;
printf("stack2 %d value is copyied to stack1",top2);
}
printf("nstack2 copyied successfully to stack1");
printf("nstack2 top2 current value=%d",top2);
printf("nstack1 top1 value=%d n",top1);
}
break;
case 3:
printf("Current queue valuen");
if(top1==-1)
{
printf("empty queuen");
break;
}
else
printf("QUEUE=");
for(i=0;i<=top1;i++)
{
printf("[%d]",stack1[i]);
}
break;
case 4:
stack1=NULL;
stack2=NULL;
free(stack1);
free(stack2);
x=x+1;
break;
default:
printf("invalid choice");
}
}
}
Here in output we have shown every case of enqueue and dequeue.
OUTPUT
enter size of array
3
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
3
Current queue value
empty queue
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
1
enter the value5
Current stack1 top1 value=-1
stack1 top1 become=0
Value enqueue successfully
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
3
Current queue value
QUEUE=[5]
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
1
enter the value6
Current stack1 top1 value=0
stack1 top1 become=1
Value enqueue successfully
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
1
enter the value7
Current stack1 top1 value=1
stack1 top1 become=2
Value enqueue successfully
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
3
Current queue value
QUEUE=[5][6][7]
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
1
overflow
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
2
stack1 current top1 value=2
starting dequeue
copy top1=2 to stack2
copy top1=1 to stack2
copy top1=0 to stack2
stack 1 is copyied to stack 2 successfully
first item of stack1 or top item of stack2 is poped
Again copying stack 2 to stack 1
current value of stack1 top1 =-1
stack1 top1 value become=0
stack2 0 value is copyied to stack1
stack1 top1 value become=1
stack2 -1 value is copyied to stack1
stack2 copyied successfully to stack1
stack2 top2 current value=-1
stack1 top1 value=1
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
3
Current queue value
QUEUE=[6][7]
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
2
stack1 current top1 value=1
starting dequeue
copy top1=1 to stack2
copy top1=0 to stack2
stack 1 is copyied to stack 2 successfully
first item of stack1 or top item of stack2 is poped
Again copying stack 2 to stack 1
current value of stack1 top1 =-1
stack1 top1 value become=0
stack2 -1 value is copyied to stack1
stack2 copyied successfully to stack1
stack2 top2 current value=-1
stack1 top1 value=0
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
2
stack1 current top1 value=0
starting dequeue
copy top1=0 to stack2
stack 1 is copyied to stack 2 successfully
first item of stack1 or top item of stack2 is poped
Again copying stack 2 to stack 1
current value of stack1 top1 =-1
stack2 copyied successfully to stack1
stack2 top2 current value=-1
stack1 top1 value=-1
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
2
underflow
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
3
Current queue value
empty queue
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE
4This program is implemented by making dequeue operation costly.So this program complexity is:-
Time Complexity:
1)Enqueue =O(1)
2)Dequeue =O(n)
2. By making enqueue costly
It is possible to implement a queue using a stack in such a way that enqueuing elements is more expensive than dequeuing elements. This can be achieved by using only one stack and enqueuing elements at the bottom of the stack rather than at the top.
When an element is added to the queue, it is pushed onto the stack. However, in order to maintain the correct order of the elements in the queue, the element must be pushed to the bottom of the stack.
To do this, all of the elements in the stack must be popped and pushed back onto the stack in the reverse order, with the new element being pushed onto the bottom of the stack.
This ensures that the element is added to the correct position in the queue, but it also increases the time complexity of enqueuing an element to O(n) in the worst case, where n is the number of elements in the queue.
Dequeuing elements from the queue is still done in O(1) time by simply popping the top element from the stack. However, because enqueuing elements is more expensive, this implementation of a queue using a stack is only efficient if the number of dequeues is much greater than the number of enqueues.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Stack data structure
typedef struct stack
{
int top;
int data[MAX_SIZE];
} stack;
// Queue data structure
typedef struct queue
{
stack enqueue_stack;
stack dequeue_stack;
} queue;
// Push element onto stack
void push(stack *s, int element)
{
if (s->top == MAX_SIZE - 1)
{
printf("Error: Stack is full.\n");
return;
}
s->data[++s->top] = element;
}
// Pop element from stack
int pop(stack *s)
{
if (s->top == -1)
{
printf("Error: Stack is empty.\n");
return -1;
}
return s->data[s->top--];
}
// Enqueue element onto queue
void enqueue(queue *q, int element)
{
// Push all elements from enqueue stack to dequeue stack
while (q->enqueue_stack.top != -1)
{
int e = pop(&q->enqueue_stack);
push(&q->dequeue_stack, e);
}
// Push element onto enqueue stack
push(&q->enqueue_stack, element);
}
// Dequeue element from queue
int dequeue(queue *q)
{
// If dequeue stack is empty, pop all elements from enqueue stack and push to dequeue stack
if (q->dequeue_stack.top == -1)
{
while (q->enqueue_stack.top != -1)
{
int e = pop(&q->enqueue_stack);
push(&q->dequeue_stack, e);
}
}
// Pop element from dequeue stack
return pop(&q->dequeue_stack);
}
// Initialize queue
void init_queue(queue *q)
{
q->enqueue_stack.top = -1;
q->dequeue_stack.top = -1;
}
int main()
{
queue q;
init_queue(&q);
// Enqueue elements onto queue
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
// Dequeue elements from queue
printf("%d\n", dequeue(&q)); // 1
printf("%d\n", dequeue(&q)); // 2
printf("%d\n", dequeue(&q)); // 3
return 0;
}
Time complexity
The time complexity of enqueuing and dequeuing elements in a queue implemented using a stack is O(1) in the best case and O(n) in the worst case, where n is the number of elements in the queue.
The best-case time complexity occurs when the dequeue stack is not empty, and the element can be popped from the stack in O(1) time.
The worst-case time complexity occurs when the dequeue stack is empty and all elements must be popped from the enqueue stack and pushed onto the dequeue stack before the element can be popped, which takes O(n) time.
Space complexity
The space complexity of a queue implemented using a stack is O(n), where n is the number of elements in the queue. This is because both the enqueue and dequeue stacks must be able to hold all of the elements in the queue in order to maintain the correct order of the elements.
In the worst case, when the queue is full, both stacks will have n elements, resulting in a space complexity of O(n).
For more competative programming check our other post too