Queue Using Linked List in C++

Introduction

A Queue is a linear data structure that follows the FIFO (First In First Out) principle. The first element inserted into the queue is the first element to be removed. Unlike an array-based queue, a Linked List Queue grows and shrinks dynamically because memory is allocated during runtime whenever a new node is inserted.

In this tutorial, we will learn how to implement a Queue using a Linked List in C++. The program performs all basic queue operations such as Enqueue, Dequeue, Front (Peek), and Display. The queue is implemented using dynamically allocated nodes along with front and rear pointers, making it an efficient solution without the size limitations of an array.

---

Table of Contents

• Algorithm
• C++ Program
• Input
• Sample Output
• Output
• Explanation
• Dry Run
• Flow of Execution
• Time Complexity
• Space Complexity
• Applications
• Key Points
• Interview Questions
• Frequently Asked Questions
• Keywords
• Conclusion

---

Algorithm

1. Start the program.
2. Create a structure Node containing data and next pointer.
3. Initialize both front and rear pointers as NULL.
4. Display the menu to the user.
5. Read the user's choice.
6. If the choice is Enqueue, create a new node and insert it at the rear of the queue.
7. If the queue is empty, update both front and rear to the new node.
8. If the choice is Dequeue, remove the node pointed to by front.
9. If after deletion the queue becomes empty, set both front and rear to NULL.
10. If the choice is Front, display the element at the front of the queue.
11. If the choice is Display, traverse the linked list from front to rear and display every element.
12. If the choice is Exit, terminate the program.
13. Otherwise, display an invalid choice message.
14. Repeat the menu until the user selects Exit.
15. Stop the program.

---

C++ Program

#include <iostream>
using namespace std;

// Node structure
struct Node
{
    int data;
    Node *next;
};

// Front and Rear pointers
Node *front = NULL;
Node *rear = NULL;

// Enqueue operation
void enqueue(int value)
{
    Node *newNode = new Node;

    newNode->data = value;
    newNode->next = NULL;

    if(front == NULL)
    {
        front = rear = newNode;
    }
    else
    {
        rear->next = newNode;
        rear = newNode;
    }

    cout << value << " inserted into queue.\n";
}

// Dequeue operation
void dequeue()
{
    if(front == NULL)
    {
        cout << "Queue Underflow! Queue is empty.\n";
        return;
    }

    Node *temp = front;

    cout << "Deleted element: " << temp->data << endl;

    front = front->next;

    if(front == NULL)
        rear = NULL;

    delete temp;
}

// Front operation
void peek()
{
    if(front == NULL)
    {
        cout << "Queue is empty.\n";
    }
    else
    {
        cout << "Front element: " << front->data << endl;
    }
}

// Display operation
void display()
{
    if(front == NULL)
    {
        cout << "Queue is empty.\n";
        return;
    }

    cout << "Queue elements are:\n";

    Node *temp = front;

    while(temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }

    cout << endl;
}

int main()
{
    int choice, value;

    do
    {
        cout << "\n===== QUEUE USING LINKED LIST =====\n";
        cout << "1. Enqueue\n";
        cout << "2. Dequeue\n";
        cout << "3. Front\n";
        cout << "4. Display\n";
        cout << "5. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;

        switch(choice)
        {
            case 1:
                cout << "Enter value to insert: ";
                cin >> value;
                enqueue(value);
                break;

            case 2:
                dequeue();
                break;

            case 3:
                peek();
                break;

            case 4:
                display();
                break;

            case 5:
                cout << "Exiting program...\n";
                break;

            default:
                cout << "Invalid choice!\n";
        }

    } while(choice != 5);

    return 0;
}

---

Input

The program accepts the user's choice from the menu. Depending on the selected option, the user may enter an integer value to insert into the queue.

1
10
1
20
1
30
4
3
2
4
5

---

Sample Output

===== QUEUE USING LINKED LIST =====
1. Enqueue
2. Dequeue
3. Front
4. Display
5. Exit
Enter your choice: 1

Enter value to insert: 10
10 inserted into queue.

===== QUEUE USING LINKED LIST =====
1. Enqueue
2. Dequeue
3. Front
4. Display
5. Exit
Enter your choice: 1

Enter value to insert: 20
20 inserted into queue.

===== QUEUE USING LINKED LIST =====
1. Enqueue
2. Dequeue
3. Front
4. Display
5. Exit
Enter your choice: 1

Enter value to insert: 30
30 inserted into queue.

===== QUEUE USING LINKED LIST =====
1. Enqueue
2. Dequeue
3. Front
4. Display
5. Exit
Enter your choice: 4

Queue elements are:
10 20 30

===== QUEUE USING LINKED LIST =====
1. Enqueue
2. Dequeue
3. Front
4. Display
5. Exit
Enter your choice: 3

Front element: 10

===== QUEUE USING LINKED LIST =====
1. Enqueue
2. Dequeue
3. Front
4. Display
5. Exit
Enter your choice: 2

Deleted element: 10

===== QUEUE USING LINKED LIST =====
1. Enqueue
2. Dequeue
3. Front
4. Display
5. Exit
Enter your choice: 4

Queue elements are:
20 30

===== QUEUE USING LINKED LIST =====
1. Enqueue
2. Dequeue
3. Front
4. Display
5. Exit
Enter your choice: 5

Exiting program...

---

---

Output

The program provides a menu-driven interface for performing various queue operations. Depending on the user's choice, it inserts a new element into the queue, removes the front element, displays the front element, or prints all queue elements from front to rear. If the queue is empty, the program displays an appropriate error message instead of performing the requested operation.

---

Explanation

Step 1

Include the required header file and use the standard namespace.

#include <iostream>
using namespace std;

• #include <iostream> provides input and output functions.
• using namespace std; allows us to use cin and cout without writing std::.

---

Step 2

Create a node structure for implementing the linked list.

struct Node
{
    int data;
    Node *next;
};

• data stores the queue element.
• next stores the address of the next node.
• Each node represents one element in the queue.

---

Step 3

Declare the front and rear pointers.

Node *front = NULL;
Node *rear = NULL;

• front always points to the first node of the queue.
• rear always points to the last node of the queue.
• Initially, both pointers are set to NULL, indicating that the queue is empty.

---

Step 4

Implement the Enqueue operation.

void enqueue(int value)
{
    Node *newNode = new Node;

    newNode->data = value;
    newNode->next = NULL;

    if(front == NULL)
    {
        front = rear = newNode;
    }
    else
    {
        rear->next = newNode;
        rear = newNode;
    }
}

• Create a new node dynamically.
• Store the given value in the node.
• If the queue is empty, both front and rear point to the new node.
• Otherwise, connect the new node to the current rear node.
• Update the rear pointer to the new node.
• The new element is inserted at the end of the queue.

---

Step 5

Implement the Dequeue operation.

void dequeue()
{
    if(front == NULL)
    {
        cout << "Queue Underflow! Queue is empty.\n";
        return;
    }

    Node *temp = front;

    front = front->next;

    if(front == NULL)
        rear = NULL;

    delete temp;
}

• Check whether the queue is empty.
• If empty, display Queue Underflow.
• Otherwise, store the front node in a temporary pointer.
• Move the front pointer to the next node.
• If the queue becomes empty after deletion, set rear to NULL.
• Delete the removed node to free the allocated memory.

---

Step 6

Implement the Front (Peek) operation.

void peek()
{
    if(front == NULL)
    {
        cout << "Queue is empty.\n";
    }
    else
    {
        cout << "Front element: "
             << front->data << endl;
    }
}

• Check whether the queue is empty.
• If the queue is empty, display an appropriate message.
• Otherwise, display the value stored at the front node.
• This operation does not remove any element from the queue.

---

Step 7

Implement the Display operation.

void display()
{
    Node *temp = front;

    while(temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

• Check whether the queue is empty.
• Create a temporary pointer pointing to the front node.
• Traverse the linked list until NULL is reached.
• Print every node during traversal.
• The elements are displayed from front to rear.

---

Step 8

Implement the main function.

int main()
{
    int choice, value;

    do
    {
        ...
    }
    while(choice != 5);

    return 0;
}

• The program repeatedly displays the menu.
• The user enters a choice.
• A switch statement performs the selected queue operation.
• The loop continues until the user selects Exit.

---

Dry Run

Input

Enqueue 10
Enqueue 20
Enqueue 30
Display
Front
Dequeue
Display

Processing

Operation	Queue (Front → Rear)	Explanation
Initially	Empty	Queue contains no elements.
Enqueue(10)	10	10 becomes both the front and rear node.
Enqueue(20)	10 → 20	20 is inserted at the rear.
Enqueue(30)	10 → 20 → 30	30 becomes the new rear node.
Display	10 20 30	Elements are displayed from front to rear.
Front	10	The first element is displayed without removing it.
Dequeue	20 → 30	10 is removed from the front of the queue.
Display	20 30	The remaining queue elements are displayed.

Output

Queue elements are:
10 20 30

Front element: 10

Deleted element: 10

Queue elements are:
20 30

---

Flow of Execution

                     Start
                       │
                       ▼
      Initialize Front = Rear = NULL
                       │
                       ▼
                Display Menu
                       │
                       ▼
              Read User Choice
                       │
 ┌─────────────┬────────────┬─────────────┐
 ▼             ▼            ▼             ▼
Enqueue     Dequeue      Front        Display
 │             │            │             │
 └─────────────┴────────────┴─────────────┘
                       │
                       ▼
              Exit Selected?
               │            │
              No           Yes
               │            │
               └────────► Stop

---

Time Complexity

Operation	Complexity
Enqueue	O(1)
Dequeue	O(1)
Front (Peek)	O(1)
Display	O(n)

Best Case: O(1)

Average Case: O(n)

Worst Case: O(n)

Overall Time Complexity:

• Enqueue: O(1)
• Dequeue: O(1)
• Front (Peek): O(1)
• Display: O(n)

Enqueue and Dequeue operations take constant time because insertion occurs at the rear and deletion occurs at the front using dedicated pointers. The Display operation traverses all nodes in the queue, resulting in linear time complexity.

---

Space Complexity

• Each inserted element requires one dynamically allocated node.
• Each node stores one integer value and one pointer.
• The program uses only one temporary pointer during traversal and deletion.

Auxiliary Space Complexity: O(1)

Total Space Complexity: O(n)

The queue grows dynamically according to the number of inserted elements. Therefore, the total memory required is directly proportional to the number of nodes present in the linked list.

---

---

Applications

• Implementing printer scheduling systems where print jobs are processed in the order they are received.
• Managing CPU scheduling using the First Come First Served (FCFS) algorithm.
• Handling customer service requests in banks, hospitals, and ticket reservation systems.
• Managing process scheduling in operating systems.
• Packet scheduling in computer networks and routers.
• Buffer management in input and output operations.
• Task scheduling in real-time systems.
• Simulation of waiting lines in various applications.
• Implementing asynchronous data processing systems.
• Learning dynamic memory allocation using linked lists in Data Structures and Algorithms (DSA).

---

Key Points

• A Queue follows the FIFO (First In First Out) principle.
• A Linked List implementation allows the queue to grow dynamically without any predefined size.
• The front pointer always points to the first node in the queue.
• The rear pointer always points to the last node in the queue.
• Enqueue() inserts a new node at the rear of the queue.
• Dequeue() removes the node from the front of the queue.
• Front() displays the first element without removing it.
• Display() traverses the queue from front to rear.
• Memory is allocated dynamically using the new operator.
• Deleted nodes are released using the delete operator.
• Enqueue, Dequeue, and Front operations require constant time O(1).
• Display operation requires linear time O(n).
• Queue Overflow generally occurs only when the system runs out of available heap memory.
• Queue Underflow occurs when attempting to delete an element from an empty queue.

---

Interview Questions

1. What is a Queue in Data Structures?
2. What does FIFO stand for?
3. Why is a Linked List preferred over an array for implementing a dynamic queue?
4. What is the purpose of the front pointer?
5. What is the purpose of the rear pointer?
6. How does the Enqueue operation work?
7. How does the Dequeue operation work?
8. What is Queue Underflow?
9. What happens when the queue becomes empty after Dequeue?
10. What is the difference between Front and Rear pointers?
11. What is the time complexity of Enqueue and Dequeue?
12. Why is dynamic memory allocation used in a Linked List Queue?
13. Can Queue Overflow occur in a Linked List implementation?
14. What are the advantages of a Linked List Queue over an Array Queue?
15. Where are Queue data structures used in real-world applications?

---

Frequently Asked Questions (FAQs)

1. What is a Queue?

A Queue is a linear data structure that follows the First In First Out (FIFO) principle, where the first inserted element is the first one to be removed.

2. Why implement a Queue using a Linked List?

A Linked List allows the queue to grow and shrink dynamically without requiring a fixed-size array, making memory management more efficient.

3. What is the purpose of the front pointer?

The front pointer always points to the first node in the queue, from where elements are removed during the Dequeue operation.

4. What is the purpose of the rear pointer?

The rear pointer always points to the last node in the queue, where new elements are inserted during the Enqueue operation.

5. What is Queue Overflow?

In a Linked List implementation, Queue Overflow generally occurs only when the system is unable to allocate additional heap memory for a new node.

6. What is Queue Underflow?

Queue Underflow occurs when an attempt is made to remove an element from an empty queue.

7. What is the time complexity of Enqueue?

The Enqueue operation has a time complexity of O(1) because insertion is always performed at the rear of the queue.

8. What is the time complexity of Dequeue?

The Dequeue operation also has a time complexity of O(1) because deletion always occurs from the front of the queue.

9. What is the time complexity of the Display operation?

Display requires traversal of all nodes from front to rear, resulting in a time complexity of O(n).

10. Why are the new and delete operators used?

The new operator dynamically allocates memory for each new node, while the delete operator releases the memory occupied by deleted nodes, preventing memory leaks.

---

Keywords

Queue Using Linked List in C++, Queue Implementation Using Linked List, Dynamic Queue in C++, Enqueue Operation in Queue, Dequeue Operation in Queue, Front Operation in Queue, Display Queue Elements, Linked List Queue Program, Queue Using Dynamic Memory Allocation, Data Structures in C++, Queue Interview Programs, C++ Queue Programs, FIFO Data Structure, Queue Operations in C++, Linked List Data Structure.

---

Conclusion

In this tutorial, we learned how to implement a Queue using a Linked List in C++. The program demonstrates all fundamental queue operations, including Enqueue, Dequeue, Front, and Display. Since memory is allocated dynamically, the queue can grow as needed without the fixed-size limitation of an array-based implementation. Enqueue and Dequeue operations execute in constant time, making the linked list implementation highly efficient for dynamic applications. Understanding this implementation builds a strong foundation for advanced data structures and prepares beginners for coding interviews and real-world programming problems involving queues.

---