Computing › Stl › Containers › Adaptors ›

Queue

A queue is an Adaptor that provides a restricted subset of Container functionality.

View version details

Contents

Definition
Description
Performance
Queue Operations
Page Comments

Key Facts

Gyroscopic Couple: The rate of change of angular momentum ( $\inline \tau$ ) = $\inline I\omega\Omega$ (In the limit).

$\inline I$ = Moment of Inertia.
$\inline \omega$ = Angular velocity
$\inline \Omega$ = Angular velocity of precession.

Definition

The queue is defined in the standard header <queue> and in the nonstandard backward-compatibility header <queue.h>.

#include<queue>
namespace std{
   template < class T, class Container = deque<T> > 
   class queue;
}

Description

A queue is a Container Adaptor that allows data to be added at one end and taken out of the other end. The deque interface is restricted (i.e., much of it is hidden) so that the required First In First Out (FIFO) queue-like behavior is provided.

Queue overflow results from trying to add an element onto a full queue and queue underflow happens when trying to remove an element from an empty queue.

A bounded queue is a queue limited to a fixed number of items.

A simple example of instantiating a queue is:

queue <int> qI; // a queue of integers
queue <double> qD; // a queue of doubles
 
// a queue of doubles stored internally in a list
queue <double, list <double> > qDoublesInList;

Performance

Queue is a container adaptor, meaning that it is implemented on top of some underlying container type like deque and list. By default, that underlying type is deque, but a different type may be selected. (see Example 2)

Queue Operations

Create, Copy and Destroy Operations

Operation	Effect
queue< El > c	Creates an empty queue c which can hold values of type El
queue< El> c1(c2)	Creates c1 as a copy of c2, whose component type must be El
queue< El > c1 = c2	Copy constructor (alternate usage syntax)

Note: Any queue will have a container data member (by default, a deque) which will hold its elements. That data member will have its own destructor which will automatically be involved when the queue goes out of scope.

Nonmodifying Operations of Queues

Operation	Effect
c1==c2	Returns if c1 is equal to c2
c1!=c2	Returns if c1 is not equal to c2
c1<c2	Returns if c1 is less than c2
c1<=c2	Returns if c1 is less than or equal to c2
c1>c2	Returns if c1 is greater than c2
c1>=c2	Returns if c1 is greater than or equal to c2
c.front()	Returns a reference to the front end component of c
c.back()	Returns a reference to the back end component of c
c.size()	Returns a value of type `size_type` giving the number of values currently in c
c.empty()	Returns true if c is empty (contains zero values), otherwise return false

Modifying Operations of Stacks

Operation	Effect
c1=c2	Assigna c2 to c1, and returns the common value. The queue on the left of an assignment receives the values and size of the one on the right
c.push(val)	Adds val to the back end of c, increasing the size of c by one
c.pop()	Removes the front end value of c, decreasing size of c by one

References:

http://www.sgi.com
Nicolai M. Josuttis: "The C++ Standard Library"

Example:

Example - simple queue of characters

Problem

This program illustrates the FIFO behavior of a simple queue of characters, as well as its default constructor, its copy constructor, and the queue push(), pop(), front(), back(),empty(),size() member functions.

Workings

#include<iostream>
#include<queue>
 
using namespace std;
 
int main
{
  queue<char> queue1;
  queue1.push('a');
  queue1.push('b');
  queue1.push('c');
 
  cout <<"\nThe queue1 contains "<<queue1.size()<<" values.";
  cout <<"\nThe front value is "<<queue1.front()<<" and the back  value is "<<queue1.back()<<".";
  cin.ignore(80, '\n');
 
  queue<char> queue2(queue1);
  queue2.push('d');
  cout <<"The queue2 is created as a copy of queue1, after which another value is added,so its size
is "<<queue2.size()<<".";
  cout <<"\nThe front value is "<<queue2.front()<<"and the back value is "<<queue2.back()<<".";
  cin.ignore(80, '\n');
 
  cout <<"\nValues of queue1, in FIFO order:\n";
  while(!queue1.empty())
  {
   cout <<queue1.front()<<"\n";
   queue1.pop();
  }
  cin.ignore(80, '\n');
 
  cout <<"\nValues of queue2, in FIFO order:\n";
  while(!queue2.empty())
  {
   cout <<queue2.front()<<"\n";
   queue2.pop();
  }
  cin.ignore(80, '\n');
 
  return 0;
}

Solution

Output:

The queue1 contains 3 values.
The front value is a and the back value is c.

The queue2 is created as a copy of queue1, after which another value is added, so its size is 4. The front value is a and the back value is d.

Values of queue1, in FIFO order:
a
b
c

Values of queue2, in FIFO order:
a
b
c
d

References:

http://www.smu.ca