Queue and Stack
◀ Vector and List - Part 2▶ STL Container Class Set Amazon
ost of you know should already how stack
work. A stack
realizes the concept of LIFO, or last in first out. Use cases are extremely common. Stack based protocol is used extensively in runtime memory management. For example the Java Virtual Machine uses stack to manage runtime memory.
A real world example of using a stack is manage cars in a single line garage. The last car parked needs to come out of the garage first.
realizes the concept of FIFO, or first in first out. Use cases are also extremely common. For example if you are writing a router application to restrict the number of internet users through this router and you want to realize “first come first serve” then you can use a queue.
Now that STL already provides template classes for stack
, you can go ahead and take advantage of them whenever you need them. Since the queue and stack have much in common conceptually, I will cover them both in this section. You need to include <stack>
) in the header to use stack and <queue>
) to use queue.
Queue and Stack are both more restrictive than vector because you cannot iterate through their elements and you cannot randomly access any element. You can only use basic operations that are defined for them.
In the following two tables, C
represents a container type including its identifier (i.e. vector<string>
is a value of the identifier. The following table shows the functions of the queue
|C & front()||returns the element at the front of the queue|
|C & back()||returns the element at the back of the queue|
|void push(const C & c)||inserts c to the back of the queue|
|void pop()||removes the element at the front of the queue|
|int size() const;||returns the number of elements in the queue|
|bool empty() const;||returns true if the queue is empty; returns false otherwise|
The following table shows the functions of the stack
|C & top()||returns the element at the top of the stack|
|void push(const C & c)||inserts c to the top of the stack|
|void pop()||removes the element at the top of the stack|
|int size() const;||returns the number of elements in the stack|
It is very straightforward to use queue and stack functions and you should already be familiar with them if you have taken a data structure course.
Next we’ll take a look at set
, another one of the most important STL containers!
◀ Vector and List - Part 2▶ STL Container Class Set