Exploring Queue Data Structure Implementation in C++

Introduction:

This code demonstrates a basic implementation of a queue data structure using linked lists. A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Elements are added to the rear and removed from the front.

#include
using namespace std;

// Structure definition for a node in the queue
struct queue
{
    int data;
    struct queue *next;
};

// Global pointers to keep track of front and rear of the queue
queue *front = NULL;
queue *rear = NULL;

// Global variable to keep track of the number of elements in the queue
int count = 0;

/********** Inserting Element in Queue ******************/
void enqueue(int x)
{
    queue *temp;
    temp = new queue();
    temp->data = x;
    temp->next = NULL;

    if (front == NULL && rear == NULL)
    {
        front = rear = temp;
        count++;
    }
    else
    {
        rear->next = temp;
        rear = temp;
        count++;
    }
}

/********* Displaying elements in Queue ********************/
void display(int count)
{
    queue *temp;
    temp = front;
    for (int i = 0; i < count; i++)
    {
        cout << temp->data << " "; temp = temp->next;
    }
}

/******* Removing element from Queue *********************/
void dequeue()
{
    if (front == NULL)
    {
        cout << "Queue is empty" << endl; } else { queue *temp; temp = front; front = front->next;
        delete temp;
        count--;

        cout << " \n Item Dequeued Successfully" << endl;
    }
}

/**************** Driver Function ************************/
int main()
{
    int choice;
    int x;

    // Enqueue loop
    do
    {
        cout << "Enter element in Queue: " << endl; cin >> x;
        enqueue(x);

        cout << "Do you want to enQueue again? (1/0): "; cin >> choice;
    } while (choice == 1);

    cout << "After Enqueue: ";
    display(count);

    // Dequeue loop
    do
    {
        dequeue();
        cout << "Do you want to DeQueue again? (1/0): "; cin >> choice;
    } while (choice == 1);

    cout << "After dequeue: ";
    display(count);

    return 0;
}

 

Code Explanation:

The code begins by defining a structure for the queue node, which contains an integer data element and a pointer to the next node. It also defines global pointers for the front and rear of the queue, and a count variable to track the number of elements.

The enqueue the function adds an element to the rear of the queue. If the queue is empty, both the front and rear are set to the new element. Otherwise, the new element is added to the rear, and the rear is updated.

The display function traverses the queue and prints its elements.

The dequeue the function removes the front element from the queue and updates the front pointer. If the queue is empty, it displays an appropriate message.

The main function provides an interactive way to enqueue and dequeue elements. It uses loops to repeatedly perform these operations based on user input.

Steps:

1. Include necessary header files.
2. Define a queue structure.
3. Declare global pointers and a count variable.
4. Implement the enqueue function to add elements to the queue.
5. Implement the display function to print elements in the queue.
6. Implement the dequeue function to remove elements from the queue.
7. Implement the main function for user interaction and demonstration.

Conclusion:

This code showcases the implementation of a queue using linked lists in C++. It allows users to enqueue and dequeue elements and displays the state of the queue before and after these operations.

FAQs:

1. What is a queue data structure?

   A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. Elements are added at one end (rear) and removed from the other end (front).

2. Why is a linked list used for implementing a queue?

   Linked lists provide efficient insertion and deletion at both ends, making them suitable for implementing queues. The front and rear pointers help maintain constant-time enqueue and dequeue operations.

3. What is the purpose of the count variable in this code?

   The count variable keeps track of the number of elements in the queue. It’s used to limit the loop in the display function and to ensure accurate indexing during traversal.

4. Can elements be enqueued after dequeuing in this code?

   Yes, the user can choose to enqueue more elements even after dequeuing. The program provides options for both enqueueing and dequeuing until the user decides to stop.

5. What is the time complexity of enqueue and dequeue operations in this code?

   Enqueue and dequeue operations both have an average time complexity of O(1), which means they take constant time regardless of the number of elements in the queue.