Queues (sstutor)

Queues

A queue is similar to a stack but it is based on the saying ‘First come first serve’. In a stack the principle is ‘last come first serve’. The concept is termed as FIFO (first-in first-out). Queues are just like queues in everyday life. The person who comes late has to stand at the end of the queue.

Similar to a stack you cannot enter in between an existing queue (i.e. you cannot insert elements into a queue); you can only keep adding to the end (back) of the queue. The two operations (of adding an element to a queue and removing an element) are called ‘pop’ and ‘push’. The only difference between the pop and push of stacks is that the elements popped and pushed are different from that of the stack.

Popping is the process of removing the first element of the queue (i.e. the element which entered the queue first).
Pushing is the process of adding an element to the back of the queue.

Diagrammatically a stack can be represented as shown below:

Text Box: Stack

Text Box: Queue

The STL has a queue template class available. The functions available are similar to those available for a stack. The basic functions needed are pop( ) and push( ). There is another function empty( ) to check whether the stack is empty. Below is a simple program to illustrate the STL queue:

//A program to illustrate the STL container for queues

#include <iostream>
#include <queue>
using namespace std;

int main( )
{
queue<int> intqueue;
int i;

//adding 5 values to the queue (0 1 2 3 4)

for(i = 0; i < 5 ; i++)
{
intqueue.push(i);
}

cout<<endl<<"The first element is : "<<intqueue.front( );
cout<<endl<<"The last element is : "<<intqueue.back( );
cout<<endl<<"The size of the queue is: "<<intqueue.size( );

//Removing the elements of the queue one by one
cout<<endl<<"Queue contents are : ";

for (i = 0; !intqueue.empty( ); i++)
{
cout<<endl<<"Element removed: "<<intqueue.front( );
intqueue.pop( );
cout<<endl<<"Size of queue after popping: "<<intqueue.size( );
}
return 0;
}

The output of the program will be:

The first element is : 0
The last element is : 4
The size of the queue is: 5
Queue contents are :

Element removed: 0
Size of queue after popping: 4
Element removed: 1
Size of queue after popping: 3
Element removed: 2
Size of queue after popping: 2
Element removed: 3
Size of queue after popping: 1
Element removed: 4
Size of queue after popping: 0

Beware: Iterators cannot be used in STL stacks and queues.

We’ll discuss more about STL and data structures later on.

Next let's take a closer look at STL

Go back to Contents page 2.