Road to C++ Programmer #12 - Container Adaptors

The container adaptors encapsulate sequence containers and provide a different interface that follows certain rules of specific data structures. In this article, we will cover three container adaptors available in the C++ Standard Library: stack, queue, and priority queue.

Stack

A stack is a data structure whose elements follow the Last-In-First-Out (LIFO) principle, meaning the element that was just pushed will be the one that gets popped first. The stack, as in memory space, is named due to this LIFO nature, which is convenient for processing function calls. It is a useful data structure for recursive algorithms and redo/undo functionalities that require access to the most recently pushed element.

#include <stack>
 
using namespace std;
 
int main () {
 
    stack<int> st;
 
    st.push(3);
    st.push(5);
    st.push(6);
 
    cout << "top: " << st.top() << endl; // => top: 6
 
    st.pop();
    cout << "top: " << st.top() << endl; // => top: 5
 
 
    return 0;
}

The above code shows how we can use a stack. By default, a stack is implemented on top of a deque, but it can be adapted to other dynamic sequence containers like vector and list by using stack<Type, Container<Type>>. The push operation adds an element to the top, while the pop operation removes the element from the top, enforcing the LIFO principle.

Queue

A queue is a data structure whose elements follow the First-In-First-Out (FIFO) principle, meaning the element that was pushed first will be the one that gets popped first. It works similarly to a line of customers waiting in front of a store, where the customer who has been waiting the longest gets to enter the store first. This is a useful data structure for sequentially processing tasks in the order they arrive, such as setting up a printer queue, an operating system's task queue, or a web server serving requests in order.

#include <queue>
 
using namespace std;
 
int main () {
 
    queue<int> q;
 
    q.push(3);
    q.push(5);
    q.push(6);
 
    cout << "front: " << q.front() << endl; // => front: 3
 
    q.pop();
    cout << "front: " << q.front() << endl; // => front: 5
 
 
    return 0;
}

The above code shows how we can use a queue. By default, a queue is implemented on top of a deque, but it can be adapted to other dynamic sequence containers by using queue<Type, Container<Type>>. The interface is quite similar to that of a stack, although the terms used are "front" and "back" instead of "top" and "bottom" to reflect the context. The push operation adds an element to the back of the queue, while the pop operation removes the element from the front, achieving FIFO.

Priority Queue

A priority queue is a queue in which elements are ordered by their priority, and the element with the highest priority is popped first. A priority queue is most useful in situations like building task scheduling algorithms where tasks have differing priorities.

#using namespace std;
 
int main () {
 
    priority_queue<int> pq;
 
    pq.push(3);
    pq.push(5);
    pq.push(6);
 
    cout << "top: " << pq.top() << endl;
 
    pq.pop();
    cout << "top: " << pq.top() << endl;
 
    return 0;
}

The above code shows how we can use a priority queue. By default, a priority queue is implemented to sort elements in ascending order and is built on top of a heap (or a binary search tree) to maintain the order of elements (which will be covered in more detail in a future article). The heap itself is implemented using a vector for efficient access to the element with the highest priority (in $O(1)$ ).

However, you can switch to other containers and modify the order by using priority_queue<Type, Container<Type>, Order<Type>>, for example priority_queue<int, deque<int>, greater<int>>. This allows you to specify the use of int, deque, and descending order. Since the priority queue is built on a binary search tree, insertion takes $O(\log(n))$ . Similarly, removing the element with the highest priority also takes $O(\log(n))$ as it may require reordering the tree.

Conclusion

In this article, we covered how stacks, queues, and priority queues work, how they are implemented, and how they can be used. This article did not focus much on the time complexity of operations, but this will be discussed in more detail in future articles, along with other data structures and algorithms.

Exercises

From this article, there will be an exercise section where you can test your understanding of the material introduced in the article. I highly recommend solving these questions by yourself after reading the main part of the article. You can click on each question to see its answer.

Resources