Queue and Stack

◀ Vector and List - Part 2▶ STL Container Class Set Amazon Most of you know should already how stack and queue 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.
A queue 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 and queue, 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> (formerly <stack.h>) in the header to use stack and <queue> (formerly <queue.h>) 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>); c is a value of the identifier. The following table shows the functions of the queue template class:

Function	Explanation
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 template class:

Function	Explanation
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