Implementation of Queue using Stack

05 min read

Implementation of queue can be done using two stacks. Queue using stack can be done in two ways.

  • By making the enqueue (insertion) operation costly.
  • By making the dequeue (deletion) operation costly.

 

Queue using stacks by making enqueue operation costly

 

Implementing queue using stacks by making the enqueue operation costly is discussed below.

  1. Initialize stack1 and stack2 making top1 = top2 = -1.
  2. To perform an enqueue operation,
  • Push all the elements from stack1 to stack2.
  • Push the new element to stack2.
  • Pop all the elements from stack2 to stack1.

    3. To perform dequeue operation,

  • Pop and return the element from stack1.

 

C program to implement queue using stacks by making enqueue operation costly

 

#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;

/* Main Function */
int main()
{
int choice;
printf("\nQUEUE USING STACKS IMPLEMENTATION\n\n");
printf("\n1.ENQUEUE");
printf("\n2.DEQUEUE");
printf("\n3.DISPLAY");
printf("\n4.EXIT");
printf("\n");
create();
while (1)
{
printf("\nEnter 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("\nInvalid 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 stack*/
int pop1()
{
return(stack1[top1--]); // Pop element from stack1
}

/*Function to push an element on to stack*/
void push2(int element)
{
stack2[++top2] = element; // Pushing the element to stack2
}

/*Function to pop an element from stack*/
int pop2()
{
return(stack2[top2--]); // pop element from stack2
}

/*Function to enqueue an element into the queue using stack*/
void enqueue()
{
int data, i;
for (i = 0;i < count;i++)
{
push2(pop1()); // Pop elements from stack1 and push them to stack2
}
printf("Enter the data : ");
scanf("%d", &data);
push1(data); // Push data from stack to the queue
count++;

for (i = 0;i < count-1;i++)
{
push1(pop2()); // Push back all the elements from stack2 to stack1
}}

/*Function to dequeue an element from the queue using stack*/
void dequeue()
{
pop1();
count--;
}

/*Function to display the elements in the queue*/
void display()
{
int i;
if(top1 == -1)
{
printf("\nEMPTY QUEUE\n");
}
else
{
printf("\nQUEUE ELEMENTS : ");
for (i = top1;i >= 0;i--)
{
printf(" %d ", stack1[i]);
}
printf("\n");
}}

 

OUTPUT

 

queue using stack

 

Queue using stacks by making dequeue operation costly

 

Implementing queue using stacks by making the dequeue operation costly is discussed below.

  1. Initialize stack1 and stack2 making top1 = top2 = -1.
  2. To perform an enqueue operation,
  • Push the element to be added to stack1.

      3. To perform dequeue operation,

  • Push all the elements from stack1 to stack2.
  • Pop and return the element from the stack2.

 

C program to implement queue using stacks by making dequeue operation costly

 

#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;

/* Main Function */
int main()
{
int choice;
printf("\nQUEUE USING STACKS IMPLEMENTATION\n\n");
printf("\n1.ENQUEUE");
printf("\n2.DEQUEUE");
printf("\n3.DISPLAY");
printf("\n4.EXIT");
printf("\n");
create();
while (1)
{
printf("\nEnter 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("\nInvalid 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 stack */
int pop1()
{
return(stack1[top1--]); // Pop element from stack1
}

/* Function to push an element on to stack */
void push2(int element)
{
stack2[++top2] = element; // Pushing the element to stack2
}

/* Function to pop an element from stack */
int pop2()
{
return(stack2[top2--]); // pop element from stack2
}

/* Function to enqueue an element into the queue using 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 stack1 and push them to stack2
}
pop2(); // Pop the element from stack2 which is the element to be dequeued
count--;
for (i = 0;i <= count;i++)
{
push1(pop2()); // Push back all the elements from stack2 to stack1
}}

/*Function to display the elements in the queue*/
void display()
{
int i;
if(top1 == -1)
{
printf("\nEMPTY QUEUE\n");
}
else
{
printf("\nQUEUE ELEMENTS : ");
for (i = 0;i <= top1;i++)
{
printf(" %d ", stack1[i]);
}
printf("\n");
}}

 

OUTPUT

 

queue using stack enqueue-costly

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error