C++ Queues | DSA in C++ - Software Development PDF Download

Introduction

Queues are an essential data structure in computer science, used to store and retrieve elements in a specific order. They follow the First-In-First-Out (FIFO) principle, where the element that is inserted first is the one that gets removed first. In this article, we will explore the concept of queues and how to implement them in C++.

What is a Queue?

A queue is a linear data structure that allows elements to be inserted at one end (rear) and removed from the other end (front). The order in which elements are inserted is the order in which they are processed or retrieved.

Queue Operations

The primary operations performed on a queue are:

• Enqueue: Adds an element to the rear of the queue.
• Dequeue: Removes the element from the front of the queue.
• Front: Returns the element at the front of the queue without removing it.
• Empty: Checks if the queue is empty.
• Size: Returns the number of elements in the queue.

Implementing a Queue in C++

There are different ways to implement a queue in C++, such as using the Standard Template Library (STL) container or implementing it from scratch using arrays or linked lists. Let's explore these implementations with code examples.

Code Examples and Explanation:

Example 1: Basic Queue Operations

#include <iostream>

#include <queue>

int main() {

    std::queue<int> myQueue;

    myQueue.push(10);

    myQueue.push(20);

    myQueue.push(30);

    std::cout << "Front element: " << myQueue.front() << std::endl;

    myQueue.pop();

    std::cout << "Front element after dequeue: " << myQueue.front() << std::endl;

    std::cout << "Queue size: " << myQueue.size() << std::endl;

    return 0;

}

Output:

Front element: 10

Front element after dequeue: 20

Queue size: 2

Explanation:

• We include the <queue> header to use the queue container from the STL.
• We create a queue named myQueue of integer type.
• We push elements 10, 20, and 30 into the queue using push() function.
• We use front() to retrieve the front element of the queue without removing it.
• We use pop() to remove the front element from the queue.
• Finally, we display the front element after dequeueing and the size of the queue.

Example 2: Queue using STL Container

#include <iostream>

#include <queue>

int main() {

    std::queue<std::string> myQueue;

    myQueue.push("Apple");

    myQueue.push("Banana");

    myQueue.push("Orange");

    while (!myQueue.empty()) {

        std::cout << myQueue.front() << " ";

        myQueue.pop();

    }

    return 0;

}

Output:

Apple Banana Orange

Explanation:

• We create a queue named 'myQueue' of string type.
• We push three string elements into the queue using 'push()' function.
• We use a while loop to print the front element and remove it from the queue using pop() until the queue becomes empty.

Example 3: Implementing a Queue using an Array

#include <iostream>

const int MAX_SIZE = 100;

class Queue {

private:

    int arr[MAX_SIZE];

    int front;

    int rear;

public:

    Queue() {

        front = -1;

        rear = -1;

    }

    bool isEmpty() {

        return (front == -1 && rear == -1);

    }

    bool isFull() {

        return (rear == MAX_SIZE - 1);

    }

    void enqueue(int data) {

        if (isFull()) {

            std::cout << "Queue is full. Cannot enqueue element." << std::endl;

            return;

        }

        if (isEmpty()) {

            front = 0;

        }

        rear++;

        arr[rear] = data;

    }

    void dequeue() {

        if (isEmpty()) {

            std::cout << "Queue is empty. Cannot dequeue element." << std::endl;

            return;

        }

        if (front == rear) {

            front = -1;

            rear = -1;

        } else {

            front++;

        }

    }

    int getFront() {

        if (isEmpty()) {

            std::cout << "Queue is empty." << std::endl;

            return -1;

        }

        return arr[front];

    }

    int getSize() {

        return (rear - front + 1);

    }

};

int main() {

    Queue myQueue;

    myQueue.enqueue(10);

    myQueue.enqueue(20);

    myQueue.enqueue(30);

    std::cout << "Front element: " << myQueue.getFront() << std::endl;

    myQueue.dequeue();

    std::cout << "Front element after dequeue: " << myQueue.getFront() << std::endl;

    std::cout << "Queue size: " << myQueue.getSize() << std::endl;

    return 0;

}

Output:

Front element: 10

Front element after dequeue: 20

Queue size: 2

Explanation:

• We create a 'Queue' class that maintains an array, 'arr', to store the elements, and two pointers, 'front' and 'rear', to keep track of the indices.
• We implement the queue operations like 'isEmpty()', 'isFull()', 'enqueue()', 'dequeue()', 'getFront()', and 'getSize()' inside the Queue class.
• We create an instance of 'Queue' named 'myQueue'.
• We enqueue three elements into the queue and display the front element, dequeue one element, and display the front element after dequeueing, and the size of the queue.

Sample Problems and Solutions

Write a C++ program to reverse the elements of a queue using a stack.

#include <iostream>

#include <queue>

#include <stack>

void reverseQueue(std::queue<int>& q) {

    std::stack<int> s;

    while (!q.empty()) {

        s.push(q.front());

        q.pop();

    }

    while (!s.empty()) {

        q.push(s.top());

        s.pop();

    }

}

int main() {

    std::queue<int> myQueue;

    myQueue.push(10);

    myQueue.push(20);

    myQueue.push(30);

    myQueue.push(40);

    myQueue.push(50);

    std::cout << "Original Queue: ";

    while (!myQueue.empty()) {

        std::cout << myQueue.front() << " ";

        myQueue.pop();

    }

    std::cout << std::endl;

    reverseQueue(myQueue);

    std::cout << "Reversed Queue: ";

    while (!myQueue.empty()) {

        std::cout << myQueue.front() << " ";

        myQueue.pop();

    }

    return 0;

}

Output:

Original Queue: 10 20 30 40 50

Reversed Queue: 50 40 30 20 10

Explanation:

• We define a function 'reverseQueue()' that takes a reference to a queue as input.
• Inside the function, we create a stack named 's'.
• We pop elements from the queue and push them into the stack until the queue becomes empty.
• Then, we pop elements from the stack and enqueue them back into the queue.
• In the 'main()' function, we create a queue named 'myQueue' and enqueue five elements into it.
• We print the original queue, call the 'reverseQueue()' function to reverse the elements, and then print the reversed queue.

Conclusion

Queues are fundamental data structures used in various applications for handling tasks in a specific order. In this article, we explored the concept of queues and how to implement them in C++. We discussed different approaches, including using the STL container and implementing a queue from scratch using arrays. By understanding and practicing queue operations, you can enhance your problem-solving skills and efficiently solve real-world challenges.
Remember to always consider the FIFO principle while working with queues, as it is the key principle that defines their behavior. With this knowledge, you are now equipped to use queues effectively in your C++ programs.