Queues

A standard queue is a FIFO ADT collection.  It stores arrivals to a service so that each item in the queue can be serviced in the order that they arrived.   The first item that arrives is the first item that gets serviced (ie FIFO).  The name of the operations vary widely with the arrival process being referred to as (insert,push, push_back, etc) and the removal from the queue being called (pop, extract, etc).   There is a builtin queue (of course) in the STL.  It is very similar to the stl::stack we discussed last week.  Here is a simple example using the STL stack. See here for reference.

#include <iostream>
#include <queue>
using namespace std;
int main()
{
 int x;
 queue<int> Q;
 for (int i = 1; i <=5; i++)
     Q.push(i);// insert a new item on the end of the queue.
 while (!Q.empty()) {
   cout<<Q.front()<<" ";//Returns the front(next item) in the Q, leaving it there.
   Q.pop(); // Removes front element and throws it away.
 }
cout << endl
return 0
}
Output: 1 2 3 4 5

Of course you can roll your own queue when you have special circumstances that need addressed.  Two usual implementations that are often done are the array implementation and the Linked list representation.  We will look at the linked list representation first.

Link List Queue

Here is a usual queue.h file you might encounter.

#include <iostream>
using namespace std;
class Queue
{
   struct Node {
     int _val;
     Node * _next;
     Node(int v, Node* n) {// I did this constructor not using the
       _val=v; // initialization list as I did before
       _next = n;
     }
 };
 Node * _front;// points to front of the list;
 Node * _last; // points to the end of the list;
 int _size;
public:
   Queue();// default constructor
   ~Queue();// destructor
   void push_back(int val);// Inserts a new item onto the end of the queue
   int front();// returns the value of the front of the queue without removing it
   void pop_front();// removes the front of the queue and throws it away
};

The implementation for the above .h file is also quite simple .  Here is one possibility.

#include "stdafx.h"
#include "Queue.h"
// default constructor
Queue::Queue()
{
 _front = _last = nullptr;
 _size = 0;
}
// destructor
Queue::~Queue()
{
 Node * tmp;
 while (_front!=nullptr) {
    tmp = _front;
    _front = _front->_next;
    delete tmp;
 }
}
// inserts a new item on the end of the queue
void Queue::push_back(int val)
{
 if (_front == nullptr) {// this empty queue special case
    _last= _front = new Node(val, nullptr);
    _size = 1;
 }
 else {
    Node * tmp = _last; // remember where the last is
    _last = new Node(val, nullptr);
    tmp->_next = _last; // Hook the new guy on the list
    _size++;
 }
}
// returns the value of the front of the queue without removing it
int Queue::front()
{
    if(_front!=nullptr)
      return _front->_val;
    cout<<"Error: asking for front of empty queue!"<<endl;
    return (-1);
}
// Removes the front of the queue and throws it away.
void Queue::pop_front()
{
 if (_front != nullptr) {
    Node * tmp = _front;
    _front = _front->_next;
    delete tmp;
    _size--;
 }
 else {
    cout << "Error: attempting to pop when queue is empty!" << endl;
 }
}

Array Implementation

In this implementation we use an array to store the queue.  This implementation takes some thought.  The main problem is that you cannot remove the first item in an array without moving every item to the left.  This is an O(n) operation that is really not acceptable.  The solution to this problem is to keep two integer indices referencing the front and end of the queue, say front and back respectively.   When we perform a pop_front() we just increment the front index and when we perform a push_back we increment the back.  Several issues arise.  How do you determine when the queue is empty, how do you determine when full and what do you do when you push_back on the queue and go off the end of the array?  A size variable easily handles the first two.  In order to deal with the last case we just index using mod the size of the array allowing wrap around to the front.  While it takes a little careful coding to pull this off it works quite well and it is quite efficient.  Its main problem is of course the limit on the number of items that can be inserted into the queue.  If one is interested, this last problem can be dealt with using stl::vectors.  I will not look at these cases since the linked list implementation and the stl::queue will handle most of you requirements.  On the other hand it is a nice programming exercise if you are interested.  Older textbooks almost always look at this array implementation method.

A UVa problem that uses a queue to solve it (10174)

Comments are closed.