---
title: "Write a program to implement a queue using two stacks."  
description: "Write a program to implement a queue using two stacks."  
author: "Utpal Vishwas"  
published: 2023-04-21  
updated: 2023-04-22  
canonical: https://www.mindstick.com/forum/157959/write-a-program-to-implement-a-queue-using-two-stacks  
category: "C Language"  
tags: ["data structure", "programs"]  
reading_time: 3 minutes  

---

# Write a program to implement a queue using two stacks.

Write a [program](https://www.mindstick.com/blog/12337/scaling-up-your-mentorship-program) to implement a [queue](https://www.mindstick.com/forum/160388/describe-the-basic-features-and-use-cases-of-the-queue-and-stack-collections-in-c-sharp) using two stacks.

## Replies

### Reply by Aryan Kumar

```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
int stack1[MAXSIZE], stack2[MAXSIZE];
int top1 = -1, top2 = -1;
void enqueue(int data) {
   if (top1 == MAXSIZE - 1) {
       printf("Queue is full, cannot enqueue.\n");
       return;
   }
   stack1[++top1] = data;
}
int dequeue() {
   if (top1 == -1 && top2 == -1) {
       printf("Queue is empty, cannot dequeue.\n");
       return -1;
   }
   if (top2 == -1) {
       while (top1 != -1) {
           stack2[++top2] = stack1[top1--];
       }
   }
   int data = stack2[top2--];
   return data;
}
int main() {
   enqueue(1);
   enqueue(2);
   enqueue(3);
   printf("%d ", dequeue());
   printf("%d ", dequeue());
   printf("%d ", dequeue());
   enqueue(4);
   enqueue(5);
   printf("%d ", dequeue());
   printf("%d\n", dequeue());
   return 0;
}
```

In this program, we implement a queue using two stacks, **stack1** and **stack2**. The **enqueue** operation is straightforward, we simply push the element onto **stack1**.

For the **dequeue** operation, we first check if both **stack1** and **stack2** are empty, in which case the queue is empty and we cannot dequeue. If **stack2** is empty, we pop all the elements from **stack1** and push them onto **stack2**, effectively reversing the order of the elements in **stack1**. Finally, we pop the top element from **stack2** and return it.

This approach ensures that the first element to be enqueued is always at the bottom of **stack1**, which becomes the top element of **stack2** after the reversal.

### Reply by Krishnapriya Rajeev

We can construct a queue using two stacks and no other temporary variables as such:

1. Construct a queue structure consisting of two stacks.
2. While enqueuing, push the items to the first stack; they get stored in the reverse order.
3. While dequeuing, pop elements from the first stack and push them to the second stack, so that the order is corrected. We can then pop the topmost element from the second stack.

The space complexity of this algorithm is O(1), as there are no temporary variables.

The time complexity for enqueue operation is O(1), however, the worst-case time complexity for the dequeue operation is O(n), since it requires us to move all elements from one stack to the other.

The code is implemented as follows:

```plaintext
#include <stdio.h>
#include <stdlib.h>
#define SIZE 64

struct Queue{
    int stack1[SIZE];       // 1st stack
    int stack2[SIZE];       // 2nd stack
    int top1,top2;
};

void enqueue(struct Queue* queue, int x){
    queue->stack1[++queue->top1] = x;       // push to 1st stack
}

int dequeue(struct Queue* queue){
    if(queue->top2 == -1){          // if 2nd stack is empty
        while(queue->top1 != -1)
            queue->stack2[++queue->top2] = queue->stack1[queue->top1--];        // pop from 1st stack and push to 2nd stack
    }
    return queue->stack2[queue->top2--];        // pop from 2nd stack
}

int main() {
    struct Queue queue;
    queue.top1 = queue.top2 = -1;

    // Enqueue elements onto queue
    enqueue(&queue, 5);
    enqueue(&queue, 10);
    enqueue(&queue, 15);

    // Dequeue elements from queue
    printf("%d ", dequeue(&queue));
    printf("%d ", dequeue(&queue));
    printf("%d ", dequeue(&queue));

    return 0;
}
```


---

Original Source: https://www.mindstick.com/forum/157959/write-a-program-to-implement-a-queue-using-two-stacks

Copyright © MindStick Software Pvt. Ltd. This Markdown version is provided for developers, AI systems, and offline reading.