Queue Implementation Using Linked List in DSA C++ - Build from Scratch

Queue Implementation Using Linked List

📖 Scenario: Imagine a line at a ticket counter where people join at the end and get served from the front. This is how a queue works. We will build a queue using a linked list in C++ to manage this line efficiently.

🎯 Goal: Build a queue using a linked list in C++. You will create nodes, add elements to the queue, remove elements from the queue, and display the queue's current state.

📋 What You'll Learn

Create a Node structure with an integer data and a pointer to the next node

Create a Queue class with pointers to the front and rear nodes

Implement enqueue to add elements at the rear

Implement dequeue to remove elements from the front

Implement a display function to show the queue elements

💡 Why This Matters

🌍 Real World

Queues are used in real life for managing lines, like in banks, supermarkets, or print jobs in computers.

💼 Career

Understanding queue implementation helps in software development roles involving data processing, task scheduling, and resource management.

1

Create Node structure and Queue class with front and rear pointers

Create a struct Node with an int data and a Node* next. Then create a class Queue with two Node* pointers named front and rear, both initialized to nullptr.

DSA C++

// Your code here

Hint

Define a Node struct with data and next. Then define a Queue class with front and rear pointers set to nullptr.

2

Add enqueue function to insert elements at the rear

Inside the Queue class, add a public method void enqueue(int value) that creates a new Node with data = value and next = nullptr. If the queue is empty (front == nullptr), set both front and rear to the new node. Otherwise, link the current rear->next to the new node and update rear to the new node.

DSA C++

#include 
using namespace std;

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

class Queue {
public:
    Node* front;
    Node* rear;

    Queue() {
        front = nullptr;
        rear = nullptr;
    }

    // Add enqueue function here
    // Your code here
};

Hint

Create a new node with the given value. If the queue is empty, set front and rear to this node. Otherwise, link the new node at the rear and update rear.

3

Add dequeue function to remove elements from the front

Inside the Queue class, add a public method void dequeue() that removes the node at the front. If the queue is empty (front == nullptr), do nothing. Otherwise, move front to front->next and delete the old front node. If after removal front becomes nullptr, set rear to nullptr as well.

DSA C++

#include 
using namespace std;

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

class Queue {
public:
    Node* front;
    Node* rear;

    Queue() {
        front = nullptr;
        rear = nullptr;
    }

    void enqueue(int value) {
        Node* newNode = new Node;
        newNode->data = value;
        newNode->next = nullptr;
        if (front == nullptr) {
            front = newNode;
            rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    // Add dequeue function here
    // Your code here
};

Hint

Check if the queue is empty. If not, remove the front node and update front. If the queue becomes empty, set rear to nullptr.

4

Add display function and print queue after operations

Inside the Queue class, add a public method void display() that prints the queue elements from front to rear separated by -> and ending with null. In main(), create a Queue object, enqueue 10, 20, 30, dequeue once, then call display().

DSA C++

#include 
using namespace std;

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

class Queue {
public:
    Node* front;
    Node* rear;

    Queue() {
        front = nullptr;
        rear = nullptr;
    }

    void enqueue(int value) {
        Node* newNode = new Node;
        newNode->data = value;
        newNode->next = nullptr;
        if (front == nullptr) {
            front = newNode;
            rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    void dequeue() {
        if (front == nullptr) {
            return;
        }
        Node* temp = front;
        front = front->next;
        delete temp;
        if (front == nullptr) {
            rear = nullptr;
        }
    }

    // Add display function here
    // Your code here
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.dequeue();
    // Call display function here
    // Your code here
    return 0;
}

Hint

Print all elements from front to rear separated by '->' and end with 'null'. In main, enqueue 10, 20, 30, dequeue once, then display.

Practice

1. What is the main advantage of implementing a queue using a linked list instead of an array?

easy

A. Dynamic size without fixed capacity

B. Faster access to middle elements

C. Uses less memory always

D. Simpler to implement than arrays

Solution

1. Step 1: Understand queue size limitation in arrays

   Arrays have fixed size, so queues implemented with arrays have a maximum capacity.

2. Step 2: Linked list dynamic size

   Linked lists can grow or shrink dynamically, so queues using linked lists do not have fixed capacity limits.

3. Final Answer:

   Dynamic size without fixed capacity -> Option A

4. Quick Check:

   Linked list queues grow dynamically = D [OK]

Hint: Linked list queues grow dynamically, arrays don't [OK]

Common Mistakes:

• Thinking linked lists use less memory always
• Confusing access speed advantages
• Assuming linked lists are simpler to implement

2. Which of the following is the correct way to declare a node structure for a queue using a linked list in C++?

easy

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

B. struct Node { int data; Node next; };

C. struct Node { int data; Node* prev; };

D. struct Node { int data; int next; };

Solution

1. Step 1: Understand node structure for linked list

   A node must contain data and a pointer to the next node.

2. Step 2: Analyze options

   struct Node { int data; Node* next; }; correctly uses a pointer to next node. struct Node { int data; Node next; }; uses next as object, which is invalid. struct Node { int data; Node* prev; }; uses prev pointer, which is for doubly linked list. struct Node { int data; int next; }; uses int for next, which is incorrect.

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option A

4. Quick Check:

   Node with data and next pointer = A [OK]

Hint: Node must have pointer to next node, not object or int [OK]

Common Mistakes:

• Using object instead of pointer for next
• Confusing singly and doubly linked list nodes
• Using int instead of pointer for next

3. What will be the output after performing these operations on an empty queue implemented using linked list?

enqueue(10); enqueue(20); dequeue(); enqueue(30); dequeue();

Print the queue elements from front to rear.

medium

A. 20 -> 30 -> null

B. 10 -> 20 -> 30 -> null

C. 30 -> null

D. 10 -> 30 -> null

Solution

1. Step 1: Perform enqueue(10) and enqueue(20)

   Queue becomes: 10 -> 20 -> null

2. Step 2: Perform dequeue()

   Removes 10, queue becomes: 20 -> null

3. Step 3: Perform enqueue(30)

   Queue becomes: 20 -> 30 -> null

4. Step 4: Perform dequeue()

   Removes 20, queue becomes: 30 -> null

5. Final Answer:

   30 -> null -> Option C

6. Quick Check:

   After operations queue front is 30 [OK]

Hint: Track enqueue/dequeue stepwise to find final queue [OK]

Common Mistakes:

• Forgetting to remove front on dequeue
• Appending dequeue element instead of removing
• Mixing order of operations

4. Identify the error in this dequeue function for a queue implemented using linked list:

int dequeue() {
  if (front == nullptr) return -1;
  Node* temp = front;
  front = front->next;
  int val = temp->data;
  delete temp;
  return val;
}

medium

A. No error, function is correct

B. Does not update rear when queue becomes empty

C. Deletes front node before accessing data

D. Returns wrong value after deletion

Solution

1. Step 1: Analyze dequeue steps

   Function removes front node and returns its data correctly.

2. Step 2: Check rear pointer update

   If after dequeue front becomes nullptr (empty queue), rear should also be set to nullptr but this is missing.

3. Final Answer:

   Does not update rear when queue becomes empty -> Option B

4. Quick Check:

   Rear must be nullptr if queue empty [OK]

Hint: Update rear to nullptr when queue becomes empty [OK]

Common Mistakes:

• Ignoring rear pointer update on empty queue
• Deleting node before reading data
• Returning wrong value after deletion

5. You want to implement a function reverseQueue() that reverses the elements of a queue implemented using a linked list without using extra arrays or STL containers. Which approach is best?

hard

A. Use recursion to dequeue elements and enqueue them back in reverse order

B. Traverse linked list and swap data of front and rear nodes repeatedly

C. Create a new linked list and insert elements at front while dequeuing

D. Use two pointers to reverse links between nodes iteratively

Solution

1. Step 1: Understand reversing linked list nodes

   Reversing links between nodes iteratively changes the queue order without extra space.

2. Step 2: Analyze options

   Use recursion to dequeue elements and enqueue them back in reverse order uses recursion but may use call stack (extra space). Traverse linked list and swap data of front and rear nodes repeatedly swaps data but is inefficient and complex. Create a new linked list and insert elements at front while dequeuing creates new list (extra space). Use two pointers to reverse links between nodes iteratively reverses links in place efficiently.

3. Final Answer:

   Use two pointers to reverse links between nodes iteratively -> Option D

4. Quick Check:

   In-place link reversal is best for linked list queue reverse [OK]

Hint: Reverse links in place with two pointers for best solution [OK]

Common Mistakes:

• Using extra arrays or containers
• Swapping data instead of links
• Using recursion causing extra space