Queue Implementation using stacks Data Structure

Queue Implementation using stacks

In this problem, we have stack data structure which supports only push() and pop() operations. We are required to implement a queue data structure using the instances of stack so we can perform operations on instances of stack only

We can implement a queue using two stacks. so we can say ‘q’ be a queue which we want to implement and ‘s1’, ‘s2’ are the stacks to be used.

So, we can implement Queue using two way and they are given below:

Method 1 (By making enqueue operation costly)

In this method, we initialize two stacks, stack1 and stack2 with Top1 = Top2 = -1.

Enqueue(s, x) operation’s step are described below:

We will push all the elements from stack1 to stack2.
Then we will push new element to stack2.
After we will pop all the elements from stack2 to stack1.

Dequeue(s) operation’s function are described below:

Pop and return the element from stack1.

Implementation: -

 #include <stdio.h>
 #include <stdlib.h>
 /* Functions and variables used */
 void push1(int);
 void push2(int);
 int pop1();
 int pop2();
 void enqueue();
 void dequeue();
 void display();
 void create();
 int stack1[100], stack2[100];
 int top1 = -1, top2 = -1;
 int count = 0;
 /* This is the Main Function */
 int main()
 {
 int choice;
 printf("\nQUEUE USING STACKS IMPLEMENTATION\n\n");
 printf("\n1. ENQUEUE ELEMENT INTO THE QUEUE ");
 printf("\n2. DEQUEUE ELEMENT FROM THE QUEUE ");
 printf("\n3. DISPLAY  ELEMENTS IN THE QUEUE ");
 printf("\n4. EXIT FROM THE PROGRAM ");
 printf("\n");
 create();
 while (1)
 {
 printf("\n Enter your choice : ");
 scanf("%d", &choice);
 switch (choice)
 {
 case 1:
 enqueue();
 break;
 case 2:
 dequeue();
 break;
 case 3:
 display();
 break;
 case 4:
 exit(0);
 default:
 printf("\n Invalid Choice \n");
 }
 }
 }
 /* Function to initialize top of two stacks*/
 void create()
 {
 top1 = top2 = -1;
 }
 /* Function to push an element to stack */
 void push1(int element)
 {
 stack1[++top1] = element; // Pushing the element to stack1
 }
 /* Function to pop element from the stack */
 int pop1()
 {
 return(stack1[top1--]); // Pop element from the stack1
 }
 /* Function to push an element on to the stack */
 void push2(int element)
 {
 stack2[++top2] = element; // Pushing the element to the stack2
 }
 /* Function to pop an element from the stack */
 int pop2()
 {
 return(stack2[top2--]); // pop element from the stack2
 }
 /* Function to enqueue an element into the queue using the stack */
 void enqueue()
 {
 int data, i;
 printf("Enter the data : ");
 scanf("%d", &data);
 push1(data); // Push data from stack to the queue
 count++;
 }
 /* Function to dequeue an element from the queue using stack */
 void dequeue()
 {
 int i;
 for (i = 0; i <= count; i++)
 {
 push2( pop1() ); // Pop elements from the stack1 and push them to the stack2
 }
 pop2(); // Pop the element from the stack2 which is the element to be dequeued
 count--;
 for (i = 0; i <= count; i++)
 {
 push1(pop2()); //  Push back all the elements from the stack2 to the stack1
 }
 }
 /*Function to display the elements in the queue*/
 void display()
 {
 int i;
 if(top1 == -1)
 {
 printf("\nEMPTY QUEUE\n");
 }
 else
 {
 printf("\nQUEUE ELEMENTS ARE :  ");
 for (i = 0; i <= top1; i++)
 {
 printf(" %d ", stack1[i]);
 }
 printf("\n");
 }
 }

Output: -

Queue Implementation using stacks Data Structure

Method 2 (By making dequeue operation costly)