Implementing Queues

Implementing queues with linked lists

We've acted now as users of queues, so it's time to act as implementers of queues. With queue, as with stack, we basically have the choice of basing our implementation on linked lists or on arrays. Once again, arrays (at least the static variety) offer the significant disadvantage of placing a limit on the number of elements allowed in the queue at any one point in time. You may decide to use dynamic arrays which overcome this limitation. However, as some of you found out with stacks, you have to be careful if you assume knowledge of the true size of the array at any given time...it's dynamic so we never truly know!

The obvious way to implement a queue is with a linked list. Since you'll be removing elements from the front of this list and adding elements to the back of the list, a linked list with both head and tail pointers is the way to go. Just as we did with stacks, we'll look at two different versions of a queue. The first is a traditional queue, the second is a more modern version.

A linked-list implementation of Queues of doubles using the traditional Queue ADT.

#ifndef _QUEUE_
#define _QUEUE_

class Queue {
public:
  Queue();
  ~Queue();
  bool isEmpty() const;
  void enqueue(const double &val);
  double dequeue();
  double peek() const;

private:
  class Node {
  public:
    double data;
    Node *next;
    Node(double v, Node *p);
  };
  Node *head, *tail;
};

#endif

#include "MyQueue.h"

Queue::Queue() {
  head = tail = 0;
}

Queue::~Queue() {
 while (!isEmpty())
   dequeue();
}

bool Queue::isEmpty() const {
  return head == 0;
}

void Queue::enqueue(const double &val) {
  if (head)
    tail = tail->next = new Node(val,0);
  else
    head = tail = new Node(val,0);
}

double Queue::dequeue() {
  Node *p = head;
  head=head->next;
  double v = p->data;
  delete p;
  if (head == 0) tail = 0;
  return v;
}

double Queue::peek() const {
  return head->data;
}

Queue::Node::Node(double v, Node *p) {
  data = v;
  next = p;
}

The implementation of a queue of doubles using the more modern queue ADT is not a whole lot different:

#ifndef _QUEUE_
#define _QUEUE_

class Queue {
public:
  Queue();
  ~Queue();
  bool isEmpty() const;
  void enqueue(const double &val);
  void dequeue();
  double getFront() const;


private:
  class Node {
  public:
    double data;
    Node *next;
    Node(double v, Node *p);
  };

  Node *head, *tail;
};

#endif

#include "MyQueueB.h"

Queue::Queue() {
  head = tail = 0;
}

Queue::~Queue() {
 while (!isEmpty())
   dequeue();
}

bool Queue::isEmpty() const{
  return head == 0;
}

void Queue::enqueue(const double &val) {
  if (head)
    tail = tail->next = new Node(val,0);
  else
    head = tail = new Node(val,0);
}

void Queue::dequeue() {
  Node *p = head;
  head=head->next;
  delete p;
  if (head == 0) tail = 0;
}

double Queue::getFront() const {
  return head->data;
}

Queue::Node::Node(double v, Node *p) {
  data = v;
  next = p;
}

Circular arrays

Implementing queues with arrays is trickier than implementing stacks. That fact might not be immediately apparent, so let's see why. With an array-based stack implementation, the bottom of the stack always stayed the same, so the indices of stack elements were always from 0 to one less than the number of elements on the stack (which is typically not the array size!). With an array-based queue implementation, elements get added to the back, which increases the index of the last element in the queue, and elements get taken off the front, which increases the index of the first element on the queue. Thus, we rapidly get to the point at which we run off the end of the array not because there are too many elements in the queue, but because the front of the queue is at an index near the back of the array. What we really want is to have any array that "wraps back around" when the index reaches the array size. So, for example, if you have an array A of 10 elements, the access of A[10] would'nt fall off the end of the array, it'd wrap around and be the same as A[0]. Similarly, A[11] would be the same as A[1], A[12] as A[2], etc. This is called a circular array, and implementing one is as simple as changing A[i] to A[i % N], where N is the number of elements in the array. Circular arrays are what we'll use to provide an array-based implmentation of queues.

The following array-based implementation of queues of doubles using the "traditional" queue ADT doesn't check for queue overflow or underflow. You might want to think about how to add it!

#ifndef _QUEUE_
#define _QUEUE_

class Queue {
public:
  Queue();
  ~Queue();
  bool isEmpty() const;
  void enqueue(const double &val);
  double dequeue();
  double peek() const;

private:
  double *A;
  int front, num_elts;
};

#endif

#include "MyQueueTA.h"
#include <iostream>

Queue::Queue() {
  front = num_elts = 0;
  A = new double[10];
}

Queue::~Queue() {
  delete [] A;
}

bool Queue::isEmpty() const {
  return num_elts == 0;
}

void Queue::enqueue(const double &val) {
  A[front+num_elts++] = val;
}

double Queue::dequeue() {
  --num_elts;
  return A[front++ % 10];
}

double Queue::peek() const {
  return A[front % 10];
}

The following array-based implementation of queues of doubles using the more modern queue ADT doesn't check for queue overflow or underflow. You might want to think about how to add it!

#ifndef _QUEUE_
#define _QUEUE_

class Queue {
public:
  Queue();
  ~Queue();
  bool isEmpty() const;
  void enqueue(const double &val);
  void dequeue();
  double getFront() const;

private:
  double *A;
  int front, num_elts;
};

#endif

#include "MyQueueBA.h"
#include <iostream>

Queue::Queue() {
  front = num_elts = 0;
  A = new double[10];
}

Queue::~Queue() {
  delete [] A;
}

bool Queue::isEmpty() const {
  return num_elts == 0;
}

void Queue::enqueue(const double &val) {
  A[front+num_elts++] = val;
}

void Queue::dequeue() {
  --num_elts;
  ++front;
}

double Queue::getFront() const {
  return A[front % 10];
}