Queue — Adaptors

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

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.

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 http://codecogs.izyba.com/reference/computing/containers/sequences/deque.php"deque" and http://codecogs.izyba.com/reference/computing/containers/sequences/list.php"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 invoked 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	Assigns 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 1

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

Example 2

Problem

This program shows how is created a queue using values from a deque and from a list, when the underlying container is a list.

Workings

#include <iostream>
#incldude <deque>
#include <queue>
#include <list>
using namespace std;

int main()
{
  int a1[] = {1, 2, 3, 4};
  deque<int> d(a1, a1+4);
  queue<int> queue1(d);
  cout <<"\nThe queue1 is created from a deque of 4 values.";
  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');

  int a2[] = {10, 11, 7, 4, 5, 25};
  list<int> lst(a2, a2+6);
  queue<int, list<int>> queue2(lst);
  cout <<"\nThe queue2 is created from a list of 6 values.";
  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 is created from a deque of 4 values.

Values of queue1, in FIFO order:
1
2
3
4

The queue2 is created from a list of 6 values.

Values of queue2, in FIFO order:
10
11
7
4
5
25

Example 3

Problem

This example of program shows the assignment of one queue to another and the comparison of queues.

Workings

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

int main()
{
  queue<int> queue1;
  queue1.push(1);
  queue1.push(2);
  queue1.push(3);
  queue1.push(4);

  cout <<"\nThe queue1 contains "<<queue1.size()<<" values.";

  // create 3 new empty queues: queue2, queue3, queue4 and assign queue1 to all 3
  queue<int> queue2, queue3, queue4;
  queue4 = queue3 = queue2 = queue1;

  cout <<"\nValues of queue1, in FIFO order:\n";
  while(!queue1.empty())
  {
    cout <<queue1.front()<<"\n";
    queue1.pop();
  }
  // display the contents of queue2 to confirm that queue1 did get assigned to queue2 

  cout <<"\nValues of queue2, in FIFO order:\n";
  while(!queue2.empty())
  {
    cout <<queue2.front()<<"\n";
    queue2.pop();
  }

  // push the value 5 onto queue4
  // output the result of comparing queue3 and queue4 using each of the relational operators

  cout <<"\nqueue3 == queue4 is "<<boolalpha<<(queue3 == queue4)<<".";
  cout <<"\nqueue3 != queue4 is "<<boolalpha<<(queue3 != queue4)<<".";
  cout <<"\nqueue3 <  queue4 is "<<boolalpha<<(queue3 <  queue4)<<".";
  cout <<"\nqueue3 <= queue4 is "<<boolalpha<<(queue3 <= queue4)<<".";
  cout <<"\nqueue3 >  queue4 is "<<boolalpha<<(queue3 >  queue4)<<".";
  cout <<"\nqueue3 >= queue4 is "<<boolalpha<<(queue3 >= queue4)<<".";

  return 0;
}

Solution

Output:

The queue1 contains 4 values.

Values of queue1, in FIFO order:
1
2
3
4

Values of queue2, in FIFO order:
1
2
3
4

queue3 == queue4 is false.

queue3 != queue4 is true.

queue3 < queue4 is true.

queue3 <= queue4 is true.

queue3 > queue4 is false.

queue3 >= queue4 is false.

References

http://www.smu.ca