ctrl + k

How to Implement a Queue from Scratch in C++

Sat Dec 16 2023 Read on Hashnode

Introduction

A queue is a data structure that stores items in a First In First Out (FIFO) manner. This means that the first item to be inserted into the queue is the first one to be removed.

we can implement a queue using an array or a linked list. In this article, we will implement a queue using a linked list.

we will use the concepts of templates, pointers, and object-oriented programming.

Queue Operations

Enqueue: Adds an item to the queue.
Dequeue: Removes an item from the queue.
Peek: Returns the front item of the queue without removing it.
IsEmpty: Checks if the queue is empty.

Queue Implementation

we will start by defining all the methods and variables that we will need in our queue class.

1
template <typename T> // T The type of elements stored in the Queue.
2
class Queue {
3

4
private:
5

6
    struct Node {
7
        T value; // Value of the node
8
        Node* next; // Pointer to the next node
9

10
        Node() {
11

12
        }
13
    };
14

15
    Node* head; // Pointer to the first node in the queue
16
    Node* tail; // Pointer to the last node in the queue
17

18
public:
19

20
    int length; // Number of elements in the queue
21

22
    Queue() {
23

24
    }
25

26
    void enqueue(T value) {
27

28
    }
29

30
    T dequeue() {
31

32
    }
33

34
    T peek() {
35

36
    }
37
};
38

39
int main () {
40

41
    // Queue q;
42

43
    return 0;
44
}

Queue class

The Queue class has two private pointers, head and tail, which point to the first and last nodes in the queue respectively. It also has a public integer length which keeps track of the number of elements in the queue. To make the queue generic, we will use templates.

1
Queue() {
2
    this->head = nullptr;
3
    this->tail = nullptr;
4
    this->length = 0;
5
}

The constructor initializes an empty queue. head and tail are set to nullptr and length is set to 0.

Node Structure

The Queue is implemented using a linked list. Each node in the list contains a value of a generic type T and a pointer to the next node. The Node structure is defined within the Queue class and is private, meaning it can only be accessed by members of the Queue class.

1
struct Node {
2
    T value;
3
    Node* next;
4

5
    Node( T value, Node* next = nullptr) {
6
        this->value = value;
7
        this->next = next;
8
    }
9
};

Node constructor takes two arguments, the value of the node and a pointer to the next node. The default value of the next pointer is nullptr. Sets the value and next variables to the passed arguments.

Enqueue

This function adds an element to the end of the queue. If the queue is empty, a new node is created and both head and tail point to it. If the queue is not empty, a new node is created and added to the end of the queue, and tail is updated to point to this new node. The length is incremented by 1.

1
void enqueue(T item) {
2
    // If the queue is empty, create a new node and set head and tail to it
3
    if (!this->tail) {
4
        this->tail = new Node(item);
5
        this->head = this->tail;
6
    }
7
    // If the queue is not empty, create a new node and add it to the end of the queue
8
    else {
9
        this->tail->next = new Node(item);
10
        this->tail = this->tail->next;
11
    }
12

13
    this->length++;
14
}

Dequeue

This function removes an element from the front of the queue. If the queue is empty, it returns a default-constructed value of type T. If the queue is not empty, it saves the value of the head node, updates head to point to the next node, deletes the old head node, and decrements length by 1. If the queue becomes empty after the dequeue operation, tail is also set to nullptr.

1
T dequeue() {
2
    if (!this->head) {
3
        return T(); // Return default-constructed value if queue is empty
4
    }
5

6
    this->length--;
7

8
    Node* previousHead = this->head;
9
    this->head = this->head->next;
10

11
    previousHead->next = nullptr;
12

13
    T previousValue = previousHead->value;
14
    delete previousHead;
15

16
    if (this->length == 0) {
17
        delete this->tail;
18
        this->tail = nullptr;
19
    }
20

21
    return previousValue;
22
}

Peek

This function returns the value of the front element without removing it. If the queue is empty, it returns a default-constructed value of type T.

1
T peek() {
2
    if (this->head) { // If the queue is not empty
3
        return this->head->value; // Return the value of the head node
4
    }
5
    return T(); // Return default-constructed value if queue is empty
6
}

IsEmpty

This function checks if the queue is empty. It returns true if length is 0, and false otherwise.

1
bool isEmpty() {
2
    return this->length == 0;
3
}

Full Code

1
#include <iostream>
2

3
template <typename T>
4
class Queue {
5

6
private:
7

8
  struct Node {
9
    T value;
10
    Node* next;
11

12
    Node(T value, Node* next = nullptr) {
13
      this->value = value;
14
      this->next = next;
15
    }
16

17
  };
18

19
  Node* head;
20
  Node* tail;
21

22
public:
23

24
  int length;
25

26
  Queue() {
27
    this->head = nullptr;
28
    this->tail = nullptr;
29
    this->length = 0;
30
  }
31

32
  void enqueue(T item) {
33
    if (!this->tail) {
34
      this->tail = new Node(item);
35
      this->head = this->tail;
36
    }
37
    else {
38
      this->tail->next = new Node(item);
39
      this->tail = this->tail->next;
40
    }
41

42
    this->length++;
43
  }
44

45
  T dequeue() {
46
    if (!this->head) {
47
      return T();
48
    }
49

50
    this->length--;
51

52
    Node* previousHead = this->head;
53
    this->head = this->head->next;
54

55
    previousHead->next = nullptr;
56

57
    T previousValue = previousHead->value;
58
    delete previousHead;
59

60
    if (this->length == 0) {
61
      delete this->tail;
62
      this->tail = nullptr;
63
    }
64

65
    return previousValue;
66

67
  }
68

69
  T peek() {
70
    if (this->head) {
71
      return this->head->value;
72
    }
73
    return T();
74
  }
75

76
  bool isEmpty() {
77
    return this->length == 0;
78
  }
79

80
};
81

82
int main() {
83

84
  Queue<int> q;
85

86
    std::cout << q.isEmpty() << '\n'; // 1
87
  q.enqueue(7);
88
  q.enqueue(3);
89
  q.enqueue(6);
90
  q.enqueue(0);
91
  std::cout << q.peek() << '\n'; // 7
92
  std::cout << q.dequeue() << '\n'; // 7
93
  std::cout << q.peek() << '\n'; // 3
94
  std::cout << q.length << '\n'; // 3
95
  std::cout << q.isEmpty() << '\n'; // 0
96

97
  return 0;
98
}