Home | Projects | Notes > Data Structures & Algorithms > Queues

Queues

Queue Using Singly-Linked List (C++)

• The only design that allows both the enqueue() and dequeue() to be of O(1) time complexity is to enqueue to the last node and dequeue from the first node.

Interface

xxxxxxxxxx
41
1
//==============================================================================
2
// File     : queue.h
3
// Brief    : Interface for Queue using Singly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : Jun 03, 2023
6
//==============================================================================
7

8
#ifndef QUEUE_H
9
#define QUEUE_H
10

11
// Class for queue (using singly-linked list) nodes
12
class Node
13
{
14
public:
15
    int value;
16
    Node *next;
17

18
    Node(int value);            // Constructor
19
};
20

21
// Class for queues (using singly-linked list)
22
class Queue
23
{
24
public:    
25
    // Public interface
26
    Queue(int value);           // Constructor  
27
    void enqueue(int value);    // Inserts a node into the last node of the queue
28
    int dequeue();              // Deletes the first node of the queue
29
    int getFirst(void);         // Returns the value of the first node of queue
30
    int getLast(void);          // Returns the number of the last node of the queue
31
    int getLength(void);        // Returns the number of the last node of the queue
32
    void printQueue(void);      // Prints all nodes in the queue
33
    ~Queue();                   // Destructor
34

35
private:
36
    Node *first;
37
    Node *last;
38
    int length;
39
};
40

41
#endif  // QUEUE_H

Implementation

xxxxxxxxxx
146
1
//==============================================================================
2
// File     : queue.cpp
3
// Brief    : Implementation of Queue using Singly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : Jun 03, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include <cstdlib>      // EXIT_FAILURE
10
#include "queue.h"
11

12

13
using namespace std;
14

15
//------------------------------------------------------------------------------
16
// Implementation of Node class interface
17
//------------------------------------------------------------------------------
18

19
// Constructor
20
// T = O(1)
21
Node::Node(int value)
22
{
23
    this->value = value;
24
    next = nullptr;
25
}
26

27
//------------------------------------------------------------------------------
28
// Implementation of Queue (using singly-linked list) class interface
29
//------------------------------------------------------------------------------
30

31
// Constructor
32
// T = O(1)
33
Queue::Queue(int value)
34
{
35
    Node *newNode = new Node(value);
36
    first = newNode;
37
    last = newNode;
38
    length = 1;
39
}
40

41
// Inserts a node into the last node of the queue
42
// T = O(1)
43
void Queue::enqueue(int value)
44
{
45
    Node *newNode = new Node(value);
46

47
    // Insert a node into an empty queue
48
    if (length == 0)    // (first == nullptr) or (last == nullptr)
49
    {
50
        first = newNode;
51
        last = newNode;
52
    }
53
    // Insert a node into a non-empty queue
54
    else
55
    {
56
        last->next = newNode;
57
        last = newNode;
58
    }
59

60
    length++;
61
}
62

63
// Deletes the first node of the queue
64
// T = O(1)
65
int Queue::dequeue(void)
66
{
67
    // Do not allow dequeue operation on an empty queue
68
    if (length == 0)
69
    {
70
        cout << "ERROR: Cannot dequeue from an empty queue. Terminating!" << endl;
71
        exit(EXIT_FAILURE);
72
    }
73

74
    Node *delNode = first;
75
    int dequeuedValue = first->value;
76

77
    // If only 1 node in the queue
78
    if (length == 1)
79
    {
80
        first == nullptr;
81
        last == nullptr;
82
    }
83
    // If 2+ nodes in the queue
84
    else
85
    {   
86
        first = first->next;
87
    }
88

89
    delete delNode;
90
    length--;
91
    
92
    return dequeuedValue;
93
}
94

95
// Returns the value of the first node of the queue
96
// T = O(1)
97
int Queue::getFirst(void)
98
{
99
    return first->value;
100
}
101

102
// Returns the value of the last node of the queue
103
// T = O(1)
104
int Queue::getLast(void)
105
{
106
    return last->value;
107
}
108

109
// Returns the number of nodes in the queue
110
// T = O(1)
111
int Queue::getLength(void)
112
{
113
    return length;
114
}
115

116
// Prints all nodes in the queue
117
// T = O(n)
118
void Queue::printQueue(void)
119
{
120
    Node *temp = first;
121

122
    while (temp)
123
    {
124
        cout << temp->value << " ";
125
        temp = temp->next;
126
    }
127

128
    cout << endl;
129
}
130

131
// Destructor
132
// T = O(n)
133
Queue::~Queue(void)
134
{
135
    // first, last, length will be destroyed by default, but the nodes will not.
136
    // So, make sure to delete them manually in the destructor.
137

138
    Node *delNode = first;
139

140
    while (first)
141
    {
142
        first = first->next;
143
        delete delNode;
144
        delNode = first;
145
    }
146
}

Test Driver

xxxxxxxxxx
42
1
//==============================================================================
2
// Filen    : main.cpp
3
// Brief    : Test driver for Queue using Singly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : Jun 03, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include "queue.h"
10

11
using namespace std;
12

13
int main(int argc, char *argv[])
14
{
15
    // Create a queue
16
    Queue *q = new Queue(4);
17
    
18
    // Enqueue nodes into the queue
19
    q->enqueue(3);
20
    q->enqueue(2);
21
    q->enqueue(1);
22

23
    // Print queue information
24
    cout << "First: " << q->getFirst() << endl;     // 4
25
    cout << "Last: " << q->getLast() << endl;       // 1
26
    cout << "Length: " << q->getLength() << endl;   // 4
27
    cout << "Queue elements: "; q->printQueue();    // 4 3 2 1
28

29
    cout << endl;
30
    
31
    // Dequeue nodes from the queue
32
    q->dequeue();
33
    q->dequeue();
34

35
    // Print queue information
36
    cout << "First: " << q->getFirst() << endl;     // 2
37
    cout << "Last: " << q->getLast() << endl;       // 1
38
    cout << "Length: " << q->getLength() << endl;   // 2
39
    cout << "Queue elements: "; q->printQueue();    // 2 1
40

41
    return 0;
42
}

xxxxxxxxxx
9
1
First: 4
2
Last: 1
3
Length: 4
4
Queue elements: 4 3 2 1 
5

6
First: 2
7
Last: 1
8
Length: 2
9
Queue elements: 2 1