Services
Technology Web App Development Mobile App Development Windows App Development Database Development UI/UX Development Cloud Development SEO Digital Marketing Guest Posting Content Writing Artificial Intelligence Data Science ERP Development CRM Development CMS Development LMS Development Business Listing Blockchain Technology Startup Promotion AI Tools Integration
Products
Data Converter Cleaner TUC - Unit Converter Import Export Survey Manager Tweet Controller
Developer
Article Blog Forum Interview Beginner News Startup Quiz
Users
Career
Apply Job Internship
Pricing
Login Sign Up Get a Quote

forum

Home Forums Write a program to implement a queue using two stacks. – MindStick
Ask Question

2 Answers

Aryan Kumar
Aryan Kumar 22 Apr 2023
Report Abuse 
#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
Krishnapriya Rajeev 21 Apr 2023
Report Abuse

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:

#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;
}
advertising
Markdown for AI

A clean, structured version of this page for AI assistants and LLMs.

Open .md