Skip to main content

Two-Stack Queue Implementation

Ayesha
EditReport

Two-Stack Queue Implementation

This project implements a queue data structure using two stacks with a lazy transfer approach. The implementation provides O(1) amortized time complexity for both enqueue and dequeue operations.

Video Explanation​

Algorithm Overview​

The implementation uses two stacks:

  • inStack: Used for enqueueing elements
  • outStack: Used for dequeueing elements

Key Operations​

  1. Enqueue: Push elements directly onto inStack - O(1)
  2. Dequeue:
    • If outStack is empty, transfer all elements from inStack to outStack
    • Pop and return the top element from outStack
    • Amortized O(1)

Implementation​

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
     int items[MAX_SIZE];
     int top;
} Stack;

typedef struct {
     Stack* inStack;
     Stack* outStack;
} Queue;

// Stack operations
void initStack(Stack* s) {
     s->top = -1;
}

bool isEmpty(Stack* s) {
     return s->top == -1;
}

bool isFull(Stack* s) {
     return s->top == MAX_SIZE - 1;
}

void push(Stack* s, int value) {
     if (!isFull(s)) {
          s->items[++s->top] = value;
     }
}

int pop(Stack* s) {
     if (!isEmpty(s)) {
          return s->items[s->top--];
     }
     return -1;  // Error value
}

Queue* createQueue() {
     Queue* q = (Queue*)malloc(sizeof(Queue));
     q->inStack = (Stack*)malloc(sizeof(Stack));
     q->outStack = (Stack*)malloc(sizeof(Stack));
     initStack(q->inStack);
     initStack(q->outStack);
     return q;
}

void enqueue(Queue* q, int value) {
     push(q->inStack, value);
}

int dequeue(Queue* q) {
     if (isEmpty(q->outStack)) {
          // Transfer elements from inStack to outStack
          while (!isEmpty(q->inStack)) {
                push(q->outStack, pop(q->inStack));
          }
     }
     return pop(q->outStack);
}

bool isQueueEmpty(Queue* q) {
     return isEmpty(q->inStack) && isEmpty(q->outStack);
}

void destroyQueue(Queue* q) {
     free(q->inStack);
     free(q->outStack);
     free(q);
}

Usage Example​

int main() {
     Queue* q = createQueue();
     
     enqueue(q, 1);
     enqueue(q, 2);
     enqueue(q, 3);
     
     printf("%d\n", dequeue(q));  // Output: 1
     printf("%d\n", dequeue(q));  // Output: 2
     
     enqueue(q, 4);
     
     printf("%d\n", dequeue(q));  // Output: 3
     printf("%d\n", dequeue(q));  // Output: 4
     
     destroyQueue(q);
     return 0;
}

Complexity​

  • Time Complexity:
    • Enqueue: O(1)O(1)
    • Dequeue: Amortized O(1)O(1)
  • Space Complexity: O(n)O(n), where nn is the number of elements in the queue.

Example​

Consider a queue with the following operations:

  1. Enqueue 1
  2. Enqueue 2
  3. Dequeue
  4. Enqueue 3
  5. Dequeue

Operations Breakdown:

  • Enqueue 1:

    • inStack: [1]
    • outStack: []

  • Enqueue 2:

    • inStack: [1, 2]
    • outStack: []

  • Dequeue:

    • Transfer elements from inStack to outStack:
      • inStack: []
      • outStack: [2, 1]
    • Pop from outStack: 1
    • Result:
      • inStack: []
      • outStack: [2]

  • Enqueue 3:

    • inStack: [3]
    • outStack: [2]

  • Dequeue:

    • Pop from outStack: 2
    • Result:
      • inStack: [3]
      • outStack: []

Conclusion​

Implementing a queue using two stacks is an efficient way to achieve the FIFO behavior with LIFO structures. This approach ensures that both the enqueue and dequeue operations have an amortized constant time complexity, making it suitable for applications where performance and resource management are critical.

Flowchart​

Track Your Progress

Done with this topic? Mark it as complete to track your progress.

đŸ’Ŧ Discuss this page

Have a question or spot something confusing in "Two-Stack Queue Implementation"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.