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

Instructions

• Attempt all the questions.
• Each question carries equal marks.
• Choose the most appropriate option for multiple-choice questions.
• Fill in the blanks by providing the correct answer.
• Answer the True/False questions with either "True" or "False."
• Hands-on questions require you to write code.

Multiple Choice Questions (MCQs)

Q.1. Which data structure is used to implement a queue?
(a) Array
(b) Linked List
(c) Stack
(d) Binary Tree

Ans. (b)

Q.2. What is the characteristic property of a queue?
(a) First-In-First-Out (FIFO)
(b) Last-In-First-Out (LIFO)
(c) Random access
(d) None of the above

Ans. (a)

Q.3. Which of the following operations are typically associated with a queue?
(a) Push and Pop
(b) Enqueue and Dequeue
(c) Insert and Delete
(d) Append and Prepend

Ans. (b)

Q.4. In a circular queue, when the rear and front pointers are at the same position, the queue is:
(a) Full
(b) Empty
(c) Overflow
(d) Underflow

Ans. (b)

Q.5. Which of the following is an advantage of using a linked list implementation of a queue?
(a) Random access to elements
(b) Constant time complexity for enqueue and dequeue operations
(c) Efficient memory utilization
(d) Fixed size

Ans. (c)

HOTS (Higher Order Thinking Skills)

Q.1. Design a C++ class to implement a queue using an array. The class should have the following member functions:

• enqueue() to insert an element at the rear of the queue
• dequeue() to remove an element from the front of the queue
• isEmpty() to check if the queue is empty
• isFull() to check if the queue is full

Implement the class and demonstrate its usage with suitable code.

#include <iostream>

#define MAX_SIZE 100

class Queue {

private:

    int arr[MAX_SIZE];

    int rear;

    int front;

public:

    Queue() {

        rear = -1;

        front = -1;

    }

    void enqueue(int value) {

        if (isFull()) {

            std::cout << "Queue is full. Overflow condition.\n";

            return;

        }

        if (isEmpty())

            front = 0;

        rear++;

        arr[rear] = value;

        std::cout << value << " enqueued successfully.\n";

    }

    void dequeue() {

        if (isEmpty()) {

            std::cout << "Queue is empty. Underflow condition.\n";

            return;

        }

        int value = arr[front];

        if (front == rear)

            front = rear = -1;

        else

            front++;

        std::cout << value << " dequeued successfully.\n";

    }

    bool isEmpty() {

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

    }

    bool isFull() {

        return (rear == MAX_SIZE - 1);

    }

};

int main() {

    Queue queue;

    queue.enqueue(5);

    queue.enqueue(10);

    queue.dequeue();

    queue.enqueue(15);

    queue.dequeue();

    queue.dequeue();

    return 0;

}

Q.2. Write a C++ function to reverse the elements of a given queue without using any additional data structure. The function should modify the original queue itself.

#include <iostream>

#include <queue>

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

    if (q.empty())

        return;

    int front = q.front();

    q.pop();

    reverseQueue(q);

    q.push(front);

}

int main() {

    std::queue<int> q;

    q.push(10);

    q.push(20);

    q.push(30);

    q.push(40);

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

    while (!q.empty()) {

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

        q.pop();

    }

    reverseQueue(q);

    std::cout << "\nReversed Queue: ";

    while (!q.empty()) {

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

        q.pop();

    }

    return 0;

}

Q.3. Implement a C++ function to find the sum of all elements in a given queue. The function should not modify the original queue.

#include <iostream>

#include <queue>

int sumQueueElements(std::queue<int> q) {

    int sum = 0;

    while (!q.empty()) {

        sum += q.front();

        q.pop();

    }

    return sum;

}

int main() {

    std::queue<int> q;

    q.push(10);

    q.push(20);

    q.push(30);

    q.push(40);

    int sum = sumQueueElements(q);

    std::cout << "Sum of elements: " << sum << std::endl;

    return 0;

}

Q.4. Write a C++ function to sort a given queue in ascending order. You can use an additional stack as an auxiliary data structure.

#include <iostream>

#include <queue>

#include <stack>

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

    std::stack<int> s;

    while (!q.empty()) {

        int temp = q.front();

        q.pop();

        while (!s.empty() && s.top() > temp) {

            q.push(s.top());

            s.pop();

        }

        s.push(temp);

    }

    while (!s.empty()) {

        q.push(s.top());

        s.pop();

    }

}

int main() {

    std::queue<int> q;

    q.push(10);

    q.push(5);

    q.push(15);

    q.push(20);

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

    while (!q.empty()) {

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

        q.pop();

    }

    sortQueue(q);

    std::cout << "\nSorted Queue: ";

    while (!q.empty()) {

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

        q.pop();

    }

    return 0;

}

Q.5. Explain the difference between a linear queue and a circular queue. When would you choose one over the other?

• Linear Queue: A linear queue is a basic queue where the elements are stored in a sequential manner. It has two ends, front and rear, and new elements are added at the rear end and removed from the front end.
• Circular Queue: A circular queue is a modified version of a linear queue where the rear end is connected to the front end, forming a circular structure. This allows efficient utilization of memory as elements can be inserted at the rear and dequeued from the front, and when the rear reaches the end, it wraps around to the front.
• When to choose one over the other: A linear queue is suitable when the size of the queue is fixed and not expected to change. It is simpler to implement and requires less memory. On the other hand, a circular queue is preferred when the size of the queue is dynamic or when efficient memory utilization is required. It allows reusing the space of dequeued elements and provides a more flexible structure.

Fill in the blanks

1. The process of adding an element to the rear end of a queue is called ________.

The process of adding an element to the rear end of a queue is called enqueue.

2. The process of removing an element from the front end of a queue is called ________.

The process of removing an element from the front end of a queue is called dequeue.

3. The operation of checking if a queue is empty is performed using the ________ function.

The operation of checking if a queue is empty is performed using the isEmpty function.

4. In a circular queue, the rear and front pointers initially point to ________.

In a circular queue, the rear and front pointers initially point to -1.

5. The time complexity for both enqueue and dequeue operations in a linked list implementation of a queue is ________.

The time complexity for both enqueue and dequeue operations in a linked list implementation of a queue is O(1).

True/False

1. In a queue, new elements are always inserted at the rear end. [True/False]

True

2. A queue can be implemented using a linked list but not using an array. [True/False]

False

3. A queue can contain elements of different data types. [True/False]

False

4. The time complexity for the enqueue operation in an array implementation of a queue is O(1). [True/False]

True

5. The main drawback of a circular queue is that it cannot grow beyond a fixed size. [True/False]

False

Hands-on Questions

Q. 1. Write a C++ program to implement a queue using a linked list. The program should have the following functions:

• enqueue() to insert an element at the rear of the queue
• dequeue() to remove an element from the front of the queue
• display() to display the elements of the queue

Test your program by performing enqueue and dequeue operations on the queue.

#include <iostream>

class Node {

public:

    int data;

    Node* next;

    Node(int value) {

        data = value;

        next = nullptr;

    }

};

class Queue {

private:

    Node* rear;

    Node* front;

public:

    Queue() {

        rear = nullptr;

        front = nullptr;

    }

    void enqueue(int value) {

        Node* newNode = new Node(value);

        if (rear == nullptr) {

            rear = newNode;

            front = newNode;

        } else {

            rear->next = newNode;

            rear = newNode;

        }

        std::cout << value << " enqueued successfully.\n";

    }

    void dequeue() {

        if (front == nullptr) {

            std::cout << "Queue is empty. Underflow condition.\n";

            return;

        }

        Node* temp = front;

        int value = temp->data;

        front = front->next;

        if (front == nullptr)

            rear = nullptr;

        delete temp;

        std::cout << value << " dequeued successfully.\n";

    }

    void display() {

        if (front == nullptr) {

            std::cout << "Queue is empty.\n";

            return;

        }

        std::cout << "Queue: ";

        Node* current = front;

        while (current != nullptr) {

            std::cout << current->data << " ";

            current = current->next;

        }

        std::cout << std::endl;

    }

};

int main() {

    Queue queue;

    queue.enqueue(5);

    queue.enqueue(10);

    queue.dequeue();

    queue.enqueue(15);

    queue.dequeue();

    queue.dequeue();

    return 0;

}

Q.2. Given an integer queue, write a C++ program to find the smallest and largest elements in the queue using a separate function. The original queue should remain unmodified.

#include <iostream>

#include <queue>

void findMinMax(std::queue<int> q, int& smallest, int& largest) {

    smallest = INT_MAX;

    largest = INT_MIN;

    while (!q.empty()) {

        int element = q.front();

        q.pop();

        smallest = std::min(smallest, element);

        largest = std::max(largest, element);

    }

}

int main() {

    std::queue<int> q;

    q.push(5);

    q.push(15);

    q.push(10);

    q.push(25);

    q.push(20);

    int smallest, largest;

    findMinMax(q, smallest, largest);

    std::cout << "Smallest element: " << smallest << std::endl;

    std::cout << "Largest element: " << largest << std::endl;

    return 0;

}

Q.3. Write a C++ program to check if a given expression containing parentheses is balanced or not using a queue.

#include <iostream>

#include <queue>

#include <stack>

bool isBalancedExpression(const std::string& expression) {

    std::queue<char> q;

    for (char c : expression) {

        if (c == '(' || c == '{' || c == '[')

            q.push(c);

        else if (c == ')' || c == '}' || c == ']') {

            if (q.empty())

                return false;

            char top = q.front();

            q.pop();

            if ((c == ')' && top != '(') ||

                (c == '}' && top != '{') ||

                (c == ']' && top != '['))

                return false;

        }

    }

    return q.empty();

}

int main() {

    std::string expression1 = "(a + b) * (c - d)";

    std::string expression2 = "{[a + b] * (c - d)}";

    std::string expression3 = "{[a + b) * (c - d)]";

    std::cout << "Expression 1 is balanced: " << std::boolalpha << isBalancedExpression(expression1) << std::endl;

    std::cout << "Expression 2 is balanced: " << std::boolalpha << isBalancedExpression(expression2) << std::endl;

    std::cout << "Expression 3 is balanced: " << std::boolalpha << isBalancedExpression(expression3) << std::endl;

    return 0;

}

Q.4. Implement a C++ program to simulate a ticket booking system using a queue. Each customer request should be enqueued, and the booking should be processed based on the first-come-first-served basis.

#include <iostream>

#include <queue>

class TicketBookingSystem {

private:

    std::queue<std::string> bookingQueue;

public:

    void bookTicket(const std::string& customerName) {

        bookingQueue.push(customerName);

        std::cout << "Booking request for " << customerName << " added to the queue.\n";

    }

    void processBooking() {

        if (bookingQueue.empty()) {

            std::cout << "No booking requests in the queue.\n";

            return;

        }

        std::string customerName = bookingQueue.front();

        bookingQueue.pop();

        std::cout << "Booking processed for " << customerName << ".\n";

    }

};

int main() {

    TicketBookingSystem bookingSystem;

    bookingSystem.processBooking();

    bookingSystem.bookTicket("Customer1");

    bookingSystem.bookTicket("Customer2");

    bookingSystem.processBooking();

    bookingSystem.processBooking();

    return 0;

}

Q.5. Write a C++ program to remove duplicate elements from a given queue.

#include <iostream>

#include <queue>

#include <unordered_set>

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

    std::unordered_set<int> uniqueElements;

    std::queue<int> tempQueue;

    while (!q.empty()) {

        int element = q.front();

        q.pop();

        if (uniqueElements.find(element) == uniqueElements.end()) {

            uniqueElements.insert(element);

            tempQueue.push(element);

        }

    }

    q = tempQueue;

}

int main() {

    std::queue<int> q;

    q.push(5);

    q.push(10);

    q.push(5);

    q.push(15);

    q.push(10);

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

    while (!q.empty()) {

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

        q.pop();

    }

    removeDuplicates(q);

    std::cout << "\nQueue after removing duplicates: ";

    while (!q.empty()) {

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

        q.pop();

    }

    return 0;

}