Implement Stack Using Queue in DSA C

Mental Model

A stack works like a pile where the last item added is the first removed. A queue works like a line where the first item added is the first removed. We can use a queue to mimic a stack by rearranging the order after each addition.

Analogy: Imagine a line of people (queue) but you want to always serve the last person who joined first (stack). After each new person joins, you make them go to the front of the line by moving everyone else behind them.

Queue: front -> [1] -> [2] -> [3] -> rear
Stack: top -> [3] -> [2] -> [1] -> bottom

Dry Run Walkthrough

Input: Push 1, Push 2, Push 3, Pop

Goal: Use a queue to behave like a stack and pop the last pushed element

Step 1: Push 1 into queue

front -> [1] -> rear

Why: Add first element normally

Step 2: Push 2 into queue, then rotate queue to move 2 to front

front -> [2] -> [1] -> rear

Why: Rotate so last pushed is at front to simulate stack top

Step 3: Push 3 into queue, then rotate queue to move 3 to front

front -> [3] -> [2] -> [1] -> rear

Why: Rotate again to keep last pushed element at front

Step 4: Pop from queue (remove front)

front -> [2] -> [1] -> rear

Why: Pop removes the last pushed element, simulating stack pop

Result:

front -> [2] -> [1] -> rear
Pop returned 3

Annotated Code

DSA C

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

#define MAX 100

typedef struct {
    int data[MAX];
    int front;
    int rear;
    int size;
} Queue;

void initQueue(Queue* q) {
    q->front = 0;
    q->rear = -1;
    q->size = 0;
}

int isEmpty(Queue* q) {
    return q->size == 0;
}

int isFull(Queue* q) {
    return q->size == MAX;
}

void enqueue(Queue* q, int val) {
    if (isFull(q)) return;
    q->rear = (q->rear + 1) % MAX;
    q->data[q->rear] = val;
    q->size++;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) return -1;
    int val = q->data[q->front];
    q->front = (q->front + 1) % MAX;
    q->size--;
    return val;
}

int queueSize(Queue* q) {
    return q->size;
}

// Stack implemented using one queue
typedef struct {
    Queue q;
} StackUsingQueue;

void initStack(StackUsingQueue* s) {
    initQueue(&s->q);
}

void push(StackUsingQueue* s, int val) {
    enqueue(&s->q, val); // add new element
    int sz = queueSize(&s->q);
    // rotate queue to move new element to front
    for (int i = 0; i < sz - 1; i++) {
        int temp = dequeue(&s->q); // remove front
        enqueue(&s->q, temp);      // add it to rear
    }
}

int pop(StackUsingQueue* s) {
    if (isEmpty(&s->q)) return -1;
    return dequeue(&s->q); // front is top of stack
}

int main() {
    StackUsingQueue s;
    initStack(&s);

    push(&s, 1);
    push(&s, 2);
    push(&s, 3);

    int val = pop(&s);
    printf("Popped: %d\n", val);

    // Print remaining stack elements
    printf("Stack after pop: ");
    while (!isEmpty(&s.q)) {
        printf("%d ", dequeue(&s.q));
    }
    printf("\n");

    return 0;
}

enqueue(&s->q, val); // add new element

Add new element to queue rear

for (int i = 0; i < sz - 1; i++) { int temp = dequeue(&s->q); enqueue(&s->q, temp); }

Rotate queue to move last pushed element to front

return dequeue(&s->q); // front is top of stack

Pop removes front element which is stack top

Output

Popped: 3

Stack after pop: 2 1 

Complexity Analysis

Time: O(n) for push because we rotate all elements to keep last pushed at front; O(1) for pop as it just dequeues front

Space: O(n) for storing n elements in the queue

vs Alternative: Naive approach using two queues can have O(1) push but O(n) pop; this approach optimizes pop to O(1) at cost of O(n) push

Edge Cases

Pop from empty stack

Returns -1 indicating stack is empty

DSA C

if (isEmpty(&s->q)) return -1;

Push into full queue

Push is ignored as queue is full, no overflow handling

DSA C

if (isFull(q)) return;

When to Use This Pattern

When you need stack behavior but only have a queue, use this pattern to reorder elements after each push so pop is efficient.

Common Mistakes

Mistake: Not rotating the queue after push, so pop returns oldest element instead of last pushed
Fix: Rotate the queue by dequeuing and enqueuing all elements except the last pushed after each push

Mistake: Trying to pop from empty queue without checking, causing errors
Fix: Check if queue is empty before dequeueing in pop

Summary

Implements a stack using a single queue by rotating elements after each push.

Use when only queue data structure is available but stack operations are needed.

The key is to rotate the queue after each push so the last pushed element is always at the front.

Practice

1. What is the main idea behind implementing a stack using a queue?

easy

A. Use one or two queues to simulate stack operations like push and pop

B. Use a queue to sort elements in ascending order

C. Use a stack to implement queue operations

D. Use two stacks to implement a queue

Solution

1. Step 1: Understand stack and queue differences

   A stack follows Last-In-First-Out (LIFO), while a queue follows First-In-First-Out (FIFO).

2. Step 2: Simulate stack using queue(s)

   By using one or two queues cleverly, we can reorder elements to behave like a stack for push and pop operations.

3. Final Answer:

   Use one or two queues to simulate stack operations like push and pop -> Option A

4. Quick Check:

   Stack via queue = simulate push/pop with queues [OK]

Hint: Remember stack is LIFO, queue is FIFO; simulate LIFO with queue(s) [OK]

Common Mistakes:

• Confusing stack and queue order
• Trying to sort elements instead of simulating stack
• Using stack to implement queue instead

2. Which of the following is the correct syntax to declare a queue in C using the standard library?

easy

A. queue<int> q;

B. struct queue q;

C. #include \nqueue q;

D. No standard queue in C; must implement manually

Solution

1. Step 1: Check C standard library support

   C language does not have a built-in queue data structure in its standard library.

2. Step 2: Understand queue implementation in C

   Queues must be implemented manually using arrays or linked lists in C.

3. Final Answer:

   No standard queue in C; must implement manually -> Option D

4. Quick Check:

   C lacks built-in queue; manual implementation needed [OK]

Hint: C has no built-in queue; implement yourself [OK]

Common Mistakes:

• Assuming C has STL-like queue
• Using C++ syntax in C code
• Including non-existent headers

3. Consider the following code snippet implementing push operation of a stack using one queue in C-like pseudocode:

void push(int x) {
    q.push(x);
    int size = q.size();
    for (int i = 0; i < size - 1; i++) {
        int val = q.front();
        q.pop();
        q.push(val);
    }
}

What will be the order of elements in the queue after pushing 1, then 2, then 3?

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. 2 -> 3 -> 1 -> null

D. 3 -> 1 -> 2 -> null

Solution

1. Step 1: Push 1

   Queue after push: [1]

2. Step 2: Push 2

   Push 2: queue becomes [1,2], then rotate first element: pop 1, push 1 -> queue is [2,1]

3. Step 3: Push 3

   Push 3: queue is [2,1,3], rotate first two elements: pop 2 push 2, pop 1 push 1 -> queue is [3,2,1]

4. Final Answer:

   3 -> 2 -> 1 -> null -> Option A

5. Quick Check:

   Newest element at front after push = 3 -> 2 -> 1 [OK]

Hint: After push, rotate queue to put new element front [OK]

Common Mistakes:

• Not rotating queue after push
• Assuming queue order is same as push order
• Confusing front and back of queue

4. The following code attempts to implement pop operation for a stack using two queues. Identify the error:

int pop() {
    if (q1.empty()) return -1;
    while (q1.size() > 1) {
        q2.push(q1.front());
        q1.pop();
    }
    int top = q1.front();
    q1.pop();
    swap(q1, q2);
    return top;
}

medium

A. The queues q1 and q2 are not initialized properly

B. The pop operation does not handle empty stack correctly

C. No error; the code correctly implements pop

D. The swap(q1, q2) should be before popping the last element

Solution

1. Step 1: Analyze pop logic

   Elements except last are moved from q1 to q2, last element is popped from q1.

2. Step 2: Swap queues

   Swapping q1 and q2 makes q1 the queue with remaining elements for next operations.

3. Final Answer:

   No error; the code correctly implements pop -> Option C

4. Quick Check:

   Pop moves all but last, returns last, swaps queues [OK]

Hint: Pop moves all but last to second queue, then swap [OK]

Common Mistakes:

• Swapping queues too early
• Not checking empty queue before pop
• Forgetting to swap queues after pop

5. You want to implement a stack using two queues. Which approach ensures that the pop() operation is O(1) time complexity, and push() is O(n)?

hard

A. Make pop costly by moving all but last from q1 to q2, then popping last from q1

B. Make push costly by pushing element to empty q2, then moving all from q1 to q2, swap q1 and q2

C. Use a single queue and rotate elements after each push

D. Use two stacks instead of queues

Solution

1. Step 1: Understand push costly approach

   Push inserts element into empty q2, moves all q1 elements to q2, then swaps q1 and q2. This makes newest element front in q1.

2. Step 2: Pop becomes O(1)

   Pop just dequeues from q1 front, which is the top of stack, so pop is O(1).

3. Final Answer:

   Make push costly by pushing element to empty q2, then moving all from q1 to q2, swap q1 and q2 -> Option B

4. Quick Check:

   Push costly + pop O(1) = push rearranges queues [OK]

Hint: Push costly rearranges queues; pop just dequeues front [OK]

Common Mistakes:

• Confusing which operation is costly
• Using single queue for O(1) pop incorrectly
• Choosing two stacks instead of queues