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

Published: 26 Nov 2024 | Reading Time: 6 min read

Introduction

Data structures such as stacks and queues play a fundamental role in computer science. They are essential for solving a wide variety of problems, and their concepts form the foundation for understanding more advanced data structures and algorithms. These data structures are often used in situations where you need to organize and process data in a specific order. These concepts are frequently asked in coding interviews and are integral to many real-world applications.

In this article, you'll understand stacks and queues, including how they work together, which is a great way to deepen your understanding.

Table of Contents

• Overview of Stack
• Overview of Queue
• Implementing Stack Using Queue
  • Approach 1: Using One Queue
  • Approach 2: Using Two Queues
• Advantages of Implementing a Stack Using Queue
• Disadvantages of Implementing a Stack Using Queue
• Conclusion
• Frequently Asked Questions

Overview of Stack

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 Stack Operations

• 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

Overview of Queue

A queue follows the First In, First Out (FIFO) principle, meaning that the first element added is the first one to be removed.

Common Queue Operations

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

Implementing Stack Using Queue

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 Queue1 (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());
    }
}

Advantages of Implementing a Stack Using Queue

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) operations

Disadvantages of Implementing a Stack Using Queue

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

Conclusion

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.

Frequently Asked Questions

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.

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.

Related Articles

• Linked List in C++: Types, Operations, and Examples
• Boyer–Moore Algorithm: Fast String Searching Explained
• Merge Two Sorted Arrays with Examples
• Insertion Sort Algorithm Explained with Examples
• Understanding the Selection Sort Algorithm
• Prime Number Program in Java: Explained with Examples

---

Source: NxtWave (CCBP.in)

Contact: [email protected] | +919390111761 (WhatsApp only)