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