STLs II
Agenda
1. Container Adaptors
○ Stack
■ Stack Properties
■ Stack Common Operations
■ Stack Traversing
■ Stack Use Cases
○ Queue
■ Queue Properties
■ Queue Common Operations
■ Queue Traversing
○ Priority Queue
■ Priority queue Properties
■ Priority queue Common Operations
■ Priority queue Traversing
2. Comparison between some Containers
3. Reasons to use C++ STL
Container Adaptors
Container adaptors are designed to make it easy to understand the concept of the
algorithm without having to clarify or comment on the algorithm steps.
They can be used to change the way data is stored and accessed, to add or
remove elements in a specific way.
Container Adaptors are divided into:
● Stack
● Queue
● Priority Queue
● Stack
#include <stack>
stack <type> name;
stack <int> st;
A stack is a container adapter that allows elements to be
added and removed from one end, known as the top. The
stack follows the Last-In-First-Out (LIFO) principle, where
the last element added to the stack will be the first to be
removed.
The stack supports three main methods: push, which adds an element to
the top of the stack; pop, which removes the top element from the stack;
and top, which returns the top element of the stack without removing it.
Stacks are used in various computer science applications, such as
expression evaluation, recursion, and undo/redo functionality. For
instance, they are used in expression evaluation to store operands and
operators and evaluate expressions in postfix notation. Also, they are used
in recursion to keep track of function calls and return addresses and in
undo/redo functionality to keep a history of changes. Overall, stacks are
an essential concept in computer science and play a significant role in
many applications.
Stack Properties:
Property Stack
Size Dynamic
Random Access No
Search No
Insert (Front Only) O(1)
Erase (Front Only) O(1)
Stack Common Operations:
stack<int> st;
st.push(10);
st.push(20);
st.pop();
st.push(5);
s.top(); // returns 5
s.empty(); // returns false
s.size(); // returns 2
Stack Traversing:
Unfortunately, the stack is not traversable in the traditional sense. The
only way to access the elements within a stack is by removing its top
element. This is because stacks operate on the principle of (LIFO).
If you need to access all the elements in a stack, you would have to
repeatedly remove the top element until the entire stack has been emptied.
// The only way to traverse a stack
while(!st.empty()){
cout << st.top() << " ";
st.pop();
}
// prints 5, 10
Stack Use Cases:
● Expression parsing
● Undo-redo operations
Example: Parenthesis matching
A common use case of stacks is in checking if a given expression has
matching parentheses. The algorithm works by iterating over the
characters of the expression and pushing each opening parenthesis onto
the stack. When a closing parenthesis is encountered, the stack is popped,
and the parentheses are checked for a match. If a match is found, the
algorithm continues to the next character. If the stack is empty or a
mismatch is found, the algorithm returns false, indicating that the
expression is invalid. Here's an example implementation of the algorithm:
bool checkParenthesis(string expr) {
stack<char> s;
for (char c: expr) {
if (c == '(')
s.push(c);
else if (c == ')') {
if (s.empty() or s.top() != '(')
return false;
else
s.pop();
}
}
return s.empty();
}
Overall we can say that stack is an abstract data type that follows the
Last-In-First-Out (LIFO) principle. It supports two basic operations: push
(add element to top) and pop (remove element from top), commonly used
to enhance algorithm clarity.
● Queue
#include <queue>
queue <type> name;
queue <int> q;
A queue is a container adapter that operates on a First-In-First-Out
(FIFO) basis, meaning that the first element added to the queue is the first
one to be removed. Elements can be inserted at one end of the queue (the
back) and removed from the other end (the front). The queue data
structure provides three main methods: push, which adds an element to
the back of the queue; pop, which removes the front element from the
queue, and front, which returns the front element without removing it.
Queues are widely used in computer science applications such as
operating systems, scheduling, and simulation. In operating systems,
queues are used to store processes waiting to be executed, with the first
process added to the queue being the first one to be executed. Similarly,
in networking, packets of data are stored in a queue until they can be
processed. Overall, queues are a fundamental concept in computer
science, much like stacks, and play a crucial role in various applications.
Queue Properties:
Property Queue
Size Dynamic
Random Access No
Search No
Insert (Back Only) O(1)
Erase (Front Only) O(1)
Queue Common Operations:
queue<int> q;
q.push(10);
q.push(20);
q.pop();
q.push(5);
Queue Traversing:
We can see that queue is similar to stack but with different order
// The only way to traverse a queue
while(!q.empty()){
cout << q.front() << " ";
q.pop();
}
// prints 10, 5
● Priority Queue
#include <queue>
priority_queue <type> name;
priority_queue <int> pq;
A priority queue is a container adapter in C++ that allows elements to be
added and removed based on their priority. Elements are stored in a way
such that the highest priority element is always at the top, and elements
with lower priority come after it. This property makes it suitable for
scenarios where processing elements based on their priority is essential,
such as in scheduling or event processing.
The priority queue supports two primary operations: push and pop. The
push operation adds an element to the priority queue based on its priority,
while the pop operation removes the highest priority element from the
priority queue. Additionally, the top operation retrieves the highest
priority element from the priority queue without removing it.
Priority queue Properties:
Property Priority queue
Size Dynamic
Random Access No
Search No
Insert O(log(n))
Erase (Highest priority) O(log(n))
Priority queue Common Operations:
Suppose we have a priority queue that stores integers in decreasing order
of their value. We can use the push operation to add elements to the
priority queue as follows:
priority_queue<int> pq;
pq.push(10);
pq.push(5);
pq.push(30);
pq.pop();
pq.push(50);
Suppose we have a priority queue of integers in increasing order of their
value. We can use the push operation to add elements to the priority
queue as follows:
priority_queue<int,vector<int>,greater<>> pq;
pq.push(10);
pq.push(5);
pq.push(30);
pq.pop();
pq.push(5);
Priority queue Traversing:
Traversing a priority queue is typically done using a loop that iteratively
removes the highest priority element and processes it. We can use the top
method to retrieve the highest priority element, and the pop method to
remove it.
// The only way to traverse a priority queue
while(!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
// prints 5, 10, 30
Overall, priority queues are an essential concept in computer science and
play a significant role in many applications where prioritisation is crucial.
The priority_queue container adapter in C++ provides an efficient way of
implementing priority queues in our programs, and understanding its
properties is essential for effectively working with it.
Comparison between some Containers
Priority
Property Array Vector Deque Stack Queue
Queue
Size Static Dynamic Dynamic Dynamic Dynamic Dynamic
Random
Yes Yes Yes No No No
access
Front/Back:
NO/new Back: O(1)
Insert array O(n) Other: O(n)
O(1) Front: O(1) Back: O(1) O(log(n))
Other: O(n)
Front/Back:
NO/new Back: O(1)
Erase array O(n) Other: O(n)
O(1) Front: O(1) Front: O(1) O(log(n))
Other: O(n)
Not Not
Ordering Ordered Ordered Ordered
applicable applicable
Ordered
Used when
Used when
frequent Used when
Used when frequent
insertion/del Used when Used when priority-bas
storing data insertion/del
etion in the LIFO FIFO ed
Usage with static
middle or
etion is
structure is structure is insertion/del
size is required in
random required required etion is
required front/back
access is required
or middle
needed
Note: The "ordering" column indicates whether the container preserves the
order in which elements were inserted. For stack and queue, this is not
applicable as they do not preserve the order. For priority queue, the ordering is
based on the priority level of the elements.
Reasons to use C++ STLs
● There is no need to develop data structures or algorithms from scratch as
C++ developers have already provided the Standard Template Library
(STL), which offers numerous benefits.
● The STL is a comprehensive library of reusable containers, iterators, and
algorithms that provide efficient, bug-free, simplified code, standardised
and well-tested solutions to common programming tasks.
● Using the STL, developers can save time and effort, reduce errors,
improve code quality, and increase productivity.
Therefore, it is highly recommended to utilise the STL and its components
whenever possible.
