C Program to Implement Stack using Two Queues

This is a C Program to implement stack using queue. The idea is pretty simple. We start with an empty queue. For the push operation we simply insert the value to be pushed into the queue. The pop operation needs some manipulation. When we need to pop from the stack (simulated with a queue), first we get the number of elements in the queue, say n, and remove (n-1) elements from the queue and keep on inserting in the queue one by one. That is, we remove the front element from the queue, and immediately insert into the queue in the rear, then we remove the front element from the queue and then immediately insert into the rear, thus we continue upto (n-1) elements. Then we will perform a remove operation, which will actually remove the nth element of the original state of the queue, and return. Note that the nth element in the queue is the one which was inserted last, and we are returning it first, therefore it works like a pop operation (Last in First Out).

Here is source code of the C Program to Implement Stack Using Two Queues. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. /* Queue structure */
  5.  
  6. #define QUEUE_EMPTY_MAGIC 0xdeadbeef
  7. typedef struct _queue_t {
  8.     int *arr;
  9.     int rear, front, count, max;
  10. } queue_t;
  11.  
  12. /* Queue operation function prototypes */
  13. queue_t *queue_allocate(int n);
  14. void queue_insert(queue_t * q, int v);
  15. int queue_remove(queue_t * q);
  16. int queue_count(queue_t * q);
  17. int queue_is_empty(queue_t * q);
  18.  
  19. /* NOTE: Here is the stuff we are interested in */
  20. /* Simulated stack operations START */
  21.  
  22. /* NOTE: passing the queue object, on which we will only operate the
  23.  * queue operations.
  24.  */
  25. void stack_push(queue_t * q, int v) {
  26.     queue_insert(q, v);
  27. }
  28.  
  29. int stack_pop(queue_t * q) {
  30.     int i, n = queue_count(q);
  31.     int removed_element;
  32.  
  33.     for (i = 0; i < (n - 1); i++) {
  34.         removed_element = queue_remove(q);
  35.         queue_insert(q, removed_element);
  36.         /* same as below */
  37.         //queue_insert (q, queue_remove (q))
  38.     }
  39.     removed_element = queue_remove(q);
  40.  
  41.     return removed_element;
  42. }
  43.  
  44. int stack_is_empty(queue_t * q) {
  45.     return queue_is_empty(q);
  46. }
  47.  
  48. int stack_count(queue_t * q) {
  49.     return queue_count(q);
  50. }
  51.  
  52. /* Simulated stack operations END */
  53.  
  54. /* Queue operations START */
  55.  
  56. int queue_count(queue_t * q) {
  57.     return q->count;
  58. }
  59.  
  60. queue_t *
  61. queue_allocate(int n) {
  62.     queue_t *queue;
  63.  
  64.     queue = malloc(sizeof(queue_t));
  65.     if (queue == NULL)
  66.         return NULL;
  67.     queue->max = n;
  68.  
  69.     queue->arr = malloc(sizeof(int) * n);
  70.     queue->rear = n - 1;
  71.     queue->front = n - 1;
  72.  
  73.     return queue;
  74. }
  75.  
  76. void queue_insert(queue_t * q, int v) {
  77.     if (q->count == q->max)
  78.         return;
  79.  
  80.     q->rear = (q->rear + 1) % q->max;
  81.     q->arr[q->rear] = v;
  82.     q->count++;
  83. }
  84.  
  85. int queue_remove(queue_t * q) {
  86.     int retval;
  87.  
  88.     /* magic number if queue is empty */
  89.     if (q->count == 0)
  90.         return QUEUE_EMPTY_MAGIC;
  91.  
  92.     q->front = (q->front + 1) % q->max;
  93.     retval = q->arr[q->front];
  94.     q->count--;
  95.  
  96.     return retval;
  97. }
  98.  
  99. int queue_is_empty(queue_t * q) {
  100.     return (q->count == 0);
  101. }
  102.  
  103. /* Queue operations END */
  104.  
  105. /* For demo */
  106. void queue_display(queue_t * q) {
  107.     int i = (q->front + 1) % q->max, elements = queue_count(q);
  108.  
  109.     while (elements--) {
  110.         printf("[%d], ", q->arr[i]);
  111.         i = (i >= q->max) ? 0 : (i + 1);
  112.     }
  113. }
  114.  
  115. #define MAX 128
  116. int main(void) {
  117.     queue_t *q;
  118.     int x, select;
  119.     /* Static allocation */
  120.     q = queue_allocate(MAX);
  121.  
  122.     do {
  123.         printf("\n[1] Push\n[2] Pop\n[0] Exit");
  124.         printf("\nChoice: ");
  125.         scanf(" %d", &select);
  126.  
  127.         switch (select) {
  128.         case 1:
  129.             printf("\nEnter value to Push:");
  130.             scanf(" %d", &x);
  131.             /* Pushing */
  132.             stack_push(q, x);
  133.  
  134.             printf("\n\n__________________________\nCurrent Queue:\n");
  135.  
  136.             queue_display(q);
  137.             printf("\n\nPushed Value: %d", x);
  138.  
  139.             printf("\n__________________________\n");
  140.             break;
  141.  
  142.         case 2:
  143.             /* Popping */
  144.             x = stack_pop(q);
  145.  
  146.             printf("\n\n\n\n__________________________\nCurrent Queue:\n");
  147.  
  148.             queue_display(q);
  149.             if (x == QUEUE_EMPTY_MAGIC)
  150.                 printf("\n\nNo values removed");
  151.             else
  152.                 printf("\n\nPopped Value: %d", x);
  153.  
  154.             printf("\n__________________________\n");
  155.             break;
  156.  
  157.         case 0:
  158.             printf("\nQutting.\n");
  159.             return 0;
  160.  
  161.         default:
  162.             printf("\nQutting.\n");
  163.             return 0;
  164.         }
  165.     } while (1);
  166.  
  167.     return 0;
  168. }

Output:

$ gcc StackUsingQueue.c
$ ./a.out
 
[1] Push
[2] Pop
[0] Exit
Choice: 1
Enter value to Push: 12
 
__________________________
Current Queue:
[12], 
 
Pushed Value: 12
__________________________
 
[1] Push
[2] Pop
[0] Exit
Choice: 1
Enter value to Push: 53
 
__________________________
Current Queue:
[12], [53], 
 
Pushed Value: 53
__________________________
 
[1] Push
[2] Pop
[0] Exit
Choice: 1
Enter value to Push: 75
 
__________________________
Current Queue:
[12], [53], [75], 
 
Pushed Value: 75
__________________________
 
[1] Push
[2] Pop
[0] Exit
Choice: 2
 
__________________________
Current Queue:
[12], [53], 
 
Popped Value: 75
__________________________
 
[1] Push
[2] Pop
[0] Exit
Choice: 0
Qutting.

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

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

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.