C Program to Implement Queue using Two Stacks

This is a C program to implement queue using two stacks.
Enqueue operation:
1. Simply push the elements into the first stack.
Dequeue operation:
1. Pop from the second stack if the second stack is not empty.
2. If second stack is empty, pop from the first stack and push all the elements into second until the first stack becomes empty.
3. Now pop an element from the second stack.

Here is the source code of the C Program. The C program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /* C program to implement queues using two stacks */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. struct node
  5. {
  6.     int data;
  7.     struct node *next;
  8. };
  9. void push(struct node** top, int data);
  10. int pop(struct node** top);
  11. struct queue
  12. {
  13.     struct node *stack1;
  14.     struct node *stack2;
  15. };
  16. void enqueue(struct queue *q, int x)
  17. {
  18.     push(&q->stack1, x);
  19. }
  20. void dequeue(struct queue *q)
  21. {
  22.     int x;
  23.     if (q->stack1 == NULL && q->stack2 == NULL) {
  24.         printf("queue is empty");
  25.         return;
  26.     }
  27.     if (q->stack2 == NULL) {
  28.         while (q->stack1 != NULL) {
  29.         x = pop(&q->stack1);
  30.         push(&q->stack2, x);
  31.         }
  32.     }
  33.     x = pop(&q->stack2);
  34.     printf("%d\n", x);
  35. }
  36. void push(struct node** top, int data)
  37. {
  38.     struct node* newnode = (struct node*) malloc(sizeof(struct node));
  39.         if (newnode == NULL) {
  40.             printf("Stack overflow \n");
  41.             return;
  42.         }
  43.     newnode->data = data;
  44.     newnode->next = (*top);
  45.     (*top) = newnode;
  46. }
  47. int pop(struct node** top)
  48. {
  49.     int buff;
  50.     struct node *t;
  51.     if (*top == NULL) {
  52.         printf("Stack underflow \n");
  53.         return;
  54.     }
  55.     else {
  56.         t = *top;
  57.         buff = t->data;
  58.         *top = t->next;
  59.         free(t);
  60.         return buff;
  61.     }
  62. }
  63. void display(struct node *top1,struct node *top2)
  64. {
  65.     while (top1 != NULL) {
  66.         printf("%d\n", top1->data);
  67.         top1 = top1->next;
  68.     }
  69.     while (top2 != NULL) {
  70.         printf("%d\n", top2->data);
  71.         top2 = top2->next;
  72.     }
  73. }
  74. int main()
  75. {
  76.     struct queue *q = (struct queue*)malloc(sizeof(struct queue));
  77.     int f = 0, a;
  78.     char ch = 'y';
  79.     q->stack1 = NULL;
  80.     q->stack2 = NULL;
  81.     while (ch == 'y'||ch == 'Y') {
  82.         printf("enter ur choice\n1.add to queue\n2.remove 
  83.                from queue\n3.display\n4.exit\n");
  84.         scanf("%d", &f);
  85.         switch(f) {
  86.             case 1 : printf("enter the element to be added to queue\n");
  87.                      scanf("%d", &a);
  88.                      enqueue(q, a);
  89.                      break;
  90.             case 2 : dequeue(q);
  91.                      break;
  92.             case 3 : display(q->stack1, q->stack2);
  93.                      break;
  94.             case 4 : exit(1);
  95.                      break;
  96.             default : printf("invalid\n");
  97.                       break;
  98.         }
  99.     }
  100. }

Output

Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
1
Enter the element to be added to queue
34
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
1
Enter the element to be added to queue
55
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
1
Enter the element to be added to queue
99
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
1
Enter the element to be added to queue
77
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
3
34
55
99
77
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
2
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
3
55
99
77
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
4

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.