Home | Projects | Notes > C++ Programming > Container Adaptor - std::queue

Container Adaptor - std::queue

std::queue

• Declared in the <queue> header file.

• First-In, First-Out (FIFO) data structure.

• Implemented as an adaptor over other STL containers.

  • Can use list, or deque as the underlying container.

  • Queue methods work through delegation—they internally call the front(), back(), push_back(), and pop_front() functions of the underlying container.

    • Since vector does not support pop_front() due to inefficiency, it cannot be used as the underlying container for queue.

• Elements are pushed at the back and popped from the front.

• Iterators are not supported.

• Use cases:

  • OS schedulers

  • Inter-task/thread communication in multi-threaded systems

  • Breadth-First Search (BFS) in graphs

  • Real-time data streams / buffers in audio/video streaming, sensor data handling

  • Printer spoolers

Initialization

Because std::queue is a container adaptor, you have the flexibility to specify the underlying container—such as deque or list—at the time of queue creation.

3
1
std::queue<int> q1;                     // deque (by default)
2
std::queue<int, std::list<int>> q2;     // list
3
std::queue<int, std::deque<int>> q3;    // deque

Note that std::queue<int, std::vector<int>> q will fail to compile because std::vector lacks pop_front().

Queue Operations

For more information, see cppreference.com.

Project: Usage of std::queue

It's best to adhere to the fundamental operations of a queue. Introducing additional methods like insert() compromises the integrity of the queue's intended behavior.

71
1
#include <iostream>
2
#include <queue>
3

4
// Prints the queue by repeatedly removing elements from the front.
5
// Note that this function is passed a queue 'by value' so whatever happens
6
// inside this function will not affect the original queue.
7
template <typename T>
8
void print(std::queue<T> q)
9
{
10
    std::cout << "[ ";
11
    while (!q.empty())
12
    {
13
        T elem = q.front();
14
        q.pop();
15
        std::cout << elem << " ";
16
    }
17
    std::cout << "]" << std::endl;
18
}
19

20
// push(), pop(), empty(), size()
21
void test(void)
22
{
23
    std::cout << "\nTEST" << std::endl;
24

25
    std::queue<int> q;
26

27
    for (int n : {1, 2, 3, 4, 5})
28
    {
29
        q.push(n);
30
    }
31
    print(q);
32

33
    std::cout << "Front: " << q.front() << std::endl;
34
    std::cout << "Back: " << q.back() << std::endl;
35

36
    q.push(100);
37
    print(q);
38

39
    q.pop();
40
    q.pop();
41
    print(q);
42

43
    while (!q.empty())
44
    {
45
        q.pop();
46
    }
47
    print(q);
48

49
    std::cout << "Size: " << q.size() << std::endl;
50

51
    q.push(10);
52
    q.push(100);
53
    q.push(1000);
54
    print(q);
55

56
    std::cout << "Front: " << q.front() << std::endl;
57
    std::cout << "Back: " << q.back() << std::endl;
58

59
    q.front() = 5;
60
    q.back() = 5000;
61

62
    print(q);
63
    std::cout << "Front: " << q.front() << std::endl;
64
    std::cout << "Back: " << q.back() << std::endl;
65
}
66

67
int main(int argc, char *argv[])
68
{
69
    test();
70
    return 0;
71
}

15
1

2
TEST
3
[ 1 2 3 4 5 ]
4
Front: 1
5
Back: 5
6
[ 1 2 3 4 5 100 ]
7
[ 3 4 5 100 ]
8
[ ]
9
Size: 0
10
[ 10 100 1000 ]
11
Front: 10
12
Back: 1000
13
[ 5 100 5000 ]
14
Front: 5
15
Back: 5000