Implementation of Stack Using a Queue in C, C++, and Java

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. In a stack, the last element added is the first one to be removed. Common operations in a stack include:

• Push: Adds an element to the stack.
• Pop: Removes the top element from the stack.
• Peek: Returns the top element without removing it.‍
• IsEmpty: Checks if the stack is empty.

A queue follows the First In, First Out (FIFO) principle, meaning that the first element added is the first one to be removed. Common operations in a queue include:

• Enqueue: Adds an element to the queue.
• Dequeue: Removes the front element from the queue.
• IsEmpty: Checks if the queue is empty.

Here are the programs to implement stack using the queue, using two main approaches:

Approach 1: Using One Queue

In this approach, we can use a single queue to simulate the stack. When an element is pushed onto the stack, we add it to the queue, but we need to rearrange the queue to make sure the most recently added element stays at the front.

Implementing Stack Using One Queue in C 

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

#define MAX_SIZE 100

typedef struct Queue {
    int arr[MAX_SIZE];
    int front, rear;
} Queue;

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

int isEmpty(Queue* q) {
    return q->front > q->rear;
}

int isFull(Queue* q) {
    return q->rear == MAX_SIZE - 1;
}

void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    q->arr[++(q->rear)] = value;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->arr[(q->front)++];
}

void push(Queue* q, int value) {
    enqueue(q, value);
    int n = q->rear - q->front;
    while (n--) {
        enqueue(q, dequeue(q));
    }
}

int pop(Queue* q) {
    if (isEmpty(q)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return dequeue(q);
}
int main() {
    Queue q;
    initQueue(&q);

    push(&q, 10);
    push(&q, 20);
    push(&q, 30);

    printf("Popped element: %d\n", pop(&q));
    printf("Popped element: %d\n", pop(&q));
    printf("Popped element: %d\n", pop(&q));

    return 0;
}

Implementing Stack Using One Queue in C++

#include <iostream>
#include <queue>

using namespace std;

class Stack {
private:
    queue<int> q;

public:
    void push(int value) {
        q.push(value);
        int n = q.size();
        for (int i = 0; i < n - 1; i++) {
            q.push(q.front());
            q.pop();
        }
    }

    int pop() {
        if (q.empty()) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        int value = q.front();
        q.pop();
        return value;
    }

    bool isEmpty() {
        return q.empty();
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Popped element: " << s.pop() << endl;
    cout << "Popped element: " << s.pop() << endl;
    cout << "Popped element: " << s.pop() << endl;

    return 0;
}

Implementing Stack Using One Queue in Java

import java.util.LinkedList;
import java.util.Queue;

class StackUsingOneQueue {
    private Queue<Integer> queue;

    public StackUsingOneQueue() {
        queue = new LinkedList<>();
    }

    public void push(int value) {
        queue.add(value);
        int n = queue.size();
        for (int i = 0; i < n - 1; i++) {
            queue.add(queue.poll());
        }
    }

    public int pop() {
        if (queue.isEmpty()) {
            System.out.println("Stack is empty!");
            return -1;
        }
        return queue.poll();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public static void main(String[] args) {
        StackUsingOneQueue stack = new StackUsingOneQueue();
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Popped element: " + stack.pop());
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Popped element: " + stack.pop());
    }
}

Approach 2: Using Two Queues

In this approach, the stack is implemented using two queues:

• Queue 1: Stores the elements of the stack.
• Queue 2: Temporarily holds elements while simulating stack behavior.

Algorithm using two queues

Push Operation

• Enqueue the new element into Queue1.
• Move all elements from Queue1 to Queue2 (so that the most recent element is at the front of Queue1).
• Swap the names of the two queues (Queue1 becomes Queue2 and vice versa).

Pop Operation

• Dequeue from Queue 1 (the front of the queue is the top element of the stack).

Peek Operation

• Return the front of Queue1 without dequeuing.

Implementing Stack Using two Queues in C

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

#define MAX_SIZE 100

typedef struct Queue {
    int arr[MAX_SIZE];
    int front, rear;
} Queue;

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

int isEmpty(Queue* q) {
    return q->front > q->rear;
}

int isFull(Queue* q) {
    return q->rear == MAX_SIZE - 1;
}

void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    q->arr[++(q->rear)] = value;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
return q->arr[(q->front)++];
}

void push(Queue* q1, Queue* q2, int value) {
    enqueue(q1, value);
}

int pop(Queue* q1, Queue* q2) {
    if (isEmpty(q1)) {
        printf("Stack is empty!\n");
        return -1;
    }

    while (q1->front != q1->rear) {
        enqueue(q2, dequeue(q1));
    }
    int value = dequeue(q1);
    // Swap references of q1 and q2 for next operation
    Queue* temp = q1;
    q1 = q2;
    q2 = temp;
    
    return value;
}

int main() {
    Queue q1, q2;
    initQueue(&q1);
    initQueue(&q2);

    push(&q1, &q2, 10);
    push(&q1, &q2, 20);
    push(&q1, &q2, 30);

    printf("Popped element: %d\n", pop(&q1, &q2));
    printf("Popped element: %d\n", pop(&q1, &q2));
    printf("Popped element: %d\n", pop(&q1, &q2));

    return 0;
}

Implementing Stack Using Two Queues in C++

#include <iostream>
#include <queue>

using namespace std;

class Stack {
private:
    queue<int> q1, q2;

public:
    void push(int value) {
        q1.push(value);
    }

    int pop() {
        if (q1.empty()) {
            cout << "Stack is empty!" << endl;
            return -1;
        }

        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop();
        }
        
        int value = q1.front();
        q1.pop();
        
        // Swap q1 and q2
        swap(q1, q2);
        
        return value;
    }

    bool isEmpty() {
        return q1.empty();
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Popped element: " << s.pop() << endl;
    cout << "Popped element: " << s.pop() << endl;
    cout << "Popped element: " << s.pop() << endl;

    return 0;
}

Implementing Stack Using Two Queues in Java

import java.util.LinkedList;
import java.util.Queue;

class StackUsingTwoQueues {
    private Queue<Integer> q1, q2;

    public StackUsingTwoQueues() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int value) {
        q1.add(value);
    }

    public int pop() {
        if (q1.isEmpty()) {
            System.out.println("Stack is empty!");
            return -1;
        }

        while (q1.size() > 1) {
            q2.add(q1.poll());
        }

        int value = q1.poll();
        
        // Swap references of q1 and q2
        Queue<Integer> temp = q1;
        q1 = q2;
		 q2 = temp;
        
        return value;
    }

    public boolean isEmpty() {
        return q1.isEmpty();
    }

    public static void main(String[] args) {
        StackUsingTwoQueues stack = new StackUsingTwoQueues();
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Popped element: " + stack.pop());
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Popped element: " + stack.pop());
    }
}

Here are the advantages of implementing a stack using a queue:

• By using a queue, insertion and deletion operations can be performed more efficiently, especially when dealing with large datasets.
• Using a queue to implement a stack can simplify the implementation process, as queues already provide the necessary FIFO (First-In-First-Out).

Here are the disadvantages of implementing a stack using a queue:

• Dequeue operation (pop) takes O(n) time, where n is the number of elements in the queue, due to the need to move all elements except the last one to another queue.
• The dequeue operation involves moving elements from one queue to another, which can be slow and inefficient.
• Requires O(n) additional space for the second queue, where n is the maximum size of the stack.

In conclusion, implementing a stack using one queue and two queues provides a viable solution, but its practicality and efficiency depend on the specific use case and requirements. Whether you're using one queue or two queues, the process of implementing stack using a queue is about managing data flow and structuring your logic.

1. What is a stack in programming? 

A stack is a data structure that follows the LIFO (Last In, First Out) principle, where elements are added to the top and removed from the top.

2. Can you implement a stack using just one queue? 

Yes, it is possible to implement a stack using a queue by using rotations, but it may not be the most efficient solution.