Write a program to implement a queue using two stacks.

Utpal Vishwas 804 21 Apr 2023

Utpal Vishwas

Student

I am Utpal Vishwas from Uttar Pradesh. Have completed my B. Tech. course from MNNIT campus Prayagraj in 2022. I have good knowledge of computer networking.

2 Answers

Aryan Kumar 22 Apr 2023

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

Krishnapriya Rajeev 21 Apr 2023

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

Construct a queue structure consisting of two stacks.
While enqueuing, push the items to the first stack; they get stored in the reverse order.
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:

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

forum

Write a program to implement a queue using two stacks.

Can you answer this question?

2 Answers