Implement Stack Using Queue in DSA C - Build from Scratch

Implement Stack Using Queue

📖 Scenario: Imagine you are building a simple text editor that needs to keep track of the last few actions a user performed. You want to use a stack to store these actions so you can undo them in reverse order. However, you only have a queue data structure available. Your task is to build a stack using a queue.

🎯 Goal: Create a stack using a single queue in C. You will implement the push and pop operations of the stack using queue operations.

📋 What You'll Learn

Create a queue structure with basic operations

Use the queue to implement stack push and pop

Demonstrate pushing and popping elements

Print the stack state after operations

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, expression evaluation, and backtracking algorithms. Sometimes you need to build one data structure using another due to system constraints.

💼 Career

Understanding how to implement one data structure using another shows problem-solving skills and deep understanding of data structures, useful for coding interviews and system design.

1

Create a queue structure

Define a struct called Queue with an integer array items of size 100, and two integers front and rear. Initialize a variable queue of type Queue with front and rear set to -1.

DSA C

// Define Queue struct and initialize queue variable
// Your code here

Hint

Use a struct with an array and two integers to track the front and rear positions.

2

Add queue helper functions

Write two functions: int isEmpty() that returns 1 if queue.front is -1, else 0; and void enqueue(int value) that adds value to the queue and updates rear and front accordingly.

DSA C

#include 
#define MAX 100

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

Queue queue = {.front = -1, .rear = -1};

// Write isEmpty() and enqueue(int value) functions
// Your code here

Hint

Check if front is -1 to detect empty queue. Add new value at rear + 1.

3

Implement stack push using queue

Write a function void push(int value) that adds value to the queue and then rotates the queue elements so that the new value is at the front, simulating stack push behavior.

DSA C

#include 
#define MAX 100

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

Queue queue = {.front = -1, .rear = -1};

int isEmpty() {
    return queue.front == -1;
}

void enqueue(int value) {
    if (queue.rear == MAX - 1) {
        return; // Queue full, ignore enqueue
    }
    if (isEmpty()) {
        queue.front = 0;
    }
    queue.rear++;
    queue.items[queue.rear] = value;
}

// Implement push(int value) to add value and rotate queue
// Your code here

Hint

After enqueue, rotate the queue by moving front elements to rear to simulate stack push.

4

Implement pop and print stack state

Write a function int pop() that removes and returns the front element of the queue (top of stack). Then, write a printStack() function that prints the queue elements from front to rear separated by -> and ending with null. Finally, push 10, 20, 30, pop once, and print the stack.

DSA C

#include 
#define MAX 100

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

Queue queue = {.front = -1, .rear = -1};

int isEmpty() {
    return queue.front == -1;
}

void enqueue(int value) {
    if (queue.rear == MAX - 1) {
        return; // Queue full, ignore enqueue
    }
    if (isEmpty()) {
        queue.front = 0;
    }
    queue.rear++;
    queue.items[queue.rear] = value;
}

void push(int value) {
    enqueue(value);
    int size = queue.rear - queue.front + 1;
    for (int i = 0; i < size - 1; i++) {
        int temp = queue.items[queue.front];
        for (int j = queue.front; j < queue.rear; j++) {
            queue.items[j] = queue.items[j + 1];
        }
        queue.items[queue.rear] = temp;
    }
}

// Implement pop() and printStack(), then push 10, 20, 30, pop once, and print stack
// Your code here

Hint

Pop removes the front element. Print elements from front to rear separated by ' -> ' and end with ' -> null'.

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