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

Queues

Introduction

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Elements are added at the back (enqueue) and removed from the front (dequeue). It is commonly used in scheduling, buffering, and breadth-first traversal scenarios.

queue-using-singly-linked-list

Pros:

Simple FIFO Logic: Maintains processing order, ideal for task scheduling and buffering.
Efficient Operations: O(1) time for enqueue and dequeue (with a linked list or circular buffer).
Flexible Implementations: Can be implemented using arrays, linked lists, or circular buffers.
Dynamic Size (Linked List): Grows as needed without reallocation.

Cons:

Limited Access: Only the front and rear elements can be accessed — no random access or indexed lookup.
Fixed Capacity (Array-Based): Unless dynamically resized, array-based queues have limited space.
Inefficient Deletion/Search: Not suitable for arbitrary removal or searching through the queue.

Compared to Stacks:

Better: When processing order must be preserved (e.g., printers, CPU scheduling).
Worse: When backtracking or nested operations are needed (stack excels there).

Implementation (C++)

Header (`queue.hpp`)


32
1
#ifndef QUEUE_HPP
2
#define QUEUE_HPP
3

4
class node
5
{
6
public:
7
    node(int val) : data(val), p_next(nullptr) {}
8

9
    int data;
10
    node *p_next;
11
};
12

13
class queue
14
{
15
public:
16
    queue();
17
    ~queue();
18
    void push(const int val);   // enqueue
19
    void pop();                 // dequeue
20
    int front() const;
21
    int back() const;
22
    bool empty() const;
23
    int size() const;
24
    void clear();
25

26
private:
27
    node *p_front;
28
    node *p_back;
29
    int cnt;
30
};
31

32
#endif

Source (`queue.cpp`)


96
1
#include "queue.hpp"
2
#include <stdexcept>
3

4
queue::queue()
5
    : p_front(nullptr), p_back(nullptr), cnt(0)
6
{
7
    // do nothing
8
}
9

10
queue::~queue()
11
{
12
    while (!empty())
13
    {
14
        pop();
15
    }
16
}
17

18
void queue::push(const int val)
19
{
20
    node *p_new = new node(val);
21

22
    if (empty())
23
    {
24
        p_front = p_back = p_new;
25
    }
26
    else
27
    {
28
        p_back->p_next = p_new;
29
        p_back = p_new;
30
    }
31

32
    ++cnt;
33
}
34

35
void queue::pop()
36
{
37
    if (empty())
38
    {
39
        throw std::runtime_error("Queue underflow");
40
    }
41

42
    node *p_del = p_front;
43
    p_front = p_front->p_next;
44
    delete p_del;
45

46
    if (nullptr == p_front)
47
    {
48
        p_back = nullptr;
49
    }
50

51
    --cnt;
52
}
53

54
int queue::front() const
55
{
56
    if (empty())
57
    {
58
        throw std::runtime_error("Queue is empty");
59
    }
60

61
    return p_front->data;
62
}
63

64
int queue::back() const
65
{
66
    if (empty())
67
    {
68
        throw std::runtime_error("Queue is empty");
69
    }
70

71
    return p_back->data;
72
}
73

74
bool queue::empty() const
75
{
76
    return 0 == cnt; // return nullptr == p_front;
77
}
78

79
int queue::size() const
80
{
81
    return cnt;
82
}
83

84
void queue::clear()
85
{
86
    while (p_front)
87
    {
88
        node *p_del = p_front;
89
        p_front = p_front->p_next;
90
        delete p_del;
91

92
        // or simply just call 'pop()' in this while loop
93
    }
94

95
    cnt = 0;
96
}

Test Driver


25
1
#include <iostream>
2
#include "queue.hpp"
3

4
int main(int argc, char *argv[])
5
{
6
    queue q;
7

8
    q.push(1);
9
    q.push(2);
10
    q.push(3);
11
    q.push(4);
12
    q.push(5);  // 1 -> 2 -> 3 -> 4 -> 5
13

14
    std::cout << q.front() << std::endl;    // 1
15
    std::cout << q.back() << std::endl;     // 5
16
    
17
    q.pop();
18
    std::cout << q.size() << std::endl;     // 4
19
    std::cout << q.empty() << std::endl;    // 0
20

21
    q.clear();
22
    std::cout << q.size() << std::endl;     // 0
23

24
    return 0;
25
}