• Queues are very straightforward but are slightly more complicated than stacks
• Queues can be implemented in a number of different ways using the same data structure (i.e., with different algorithms)
• So, they are a good ADT to consider next

• When you add a person to the line they go to the back
• People are served from the front (first-in-first-out or FIFO)

Queue

Values:	Homogeneous elements of any type.
Operations:	Name/Operator Arguments Returns Constructor A new instance. enqueue/append element The element to add to the rear of the queue dequeue/serve The element at the front of the queue isEmpty true if the queue is empty and false o/w

In addition, if the stack has a "size limit", one could add an isFull() operation; some people add a peek() operation; and some people add a makeEmpty() operation.

• Enqueue/append to the rear
• Dequeue/serve from the front (index 0)
• "Shuffle" after each serve
• An Analogy: A normal waiting line

cppexamples/arrayqueue/shuffling/Queue.h

        #ifndef edu_jmu_cs_Queue_h
#define edu_jmu_cs_Queue_h

const int maxqueue = 10;

/**
 * A Queue (FIFO list) class
 *
 * @author Prof. David Bernstein, James Madison University
 */
class Queue {
 public:
  /**
   * Default constructor
   */
  Queue();

  /**
   * Remove and return an element from the front of the queue
   *
   * @return The front element
   */
  int dequeue(void);

  /**
   * Append an element onto the end of the queue
   *
   * @param item   The element to append
   */
  void enqueue(int item);

  /**
   * Is this Queue empty?
   *
   * @return true if the queue is empty and false otherwise
   */
  bool isEmpty(void);

 private:
  int count;

  // The array containing the items
  int entry[maxqueue];
};

#endif
        

cppexamples/arrayqueue/shuffling/Queue.cpp

        #include "Queue.h"

/**
 * This implementation uses an array and "shuffles" the entries
 * every time an element is served
 */
Queue::Queue() {
  count = 0;
}

int Queue::dequeue(void) {
  int i, item;

  if (count <= 0) {
    item = -1;
  } else {
    item = entry[0];
    count--;

    for (i = 0; i < count; i++)
      entry[i] = entry[i + 1];
  }
  return item;
}

void Queue::enqueue(int item) {
  if (count < maxqueue) {
    entry[count] = item;
    count++;
  }
}

bool Queue::isEmpty(void) {
  bool result;

  if (count == 0)
    result = true;
  else
    result = false;

  return result;
}
        

• Keep a "pointer" to the front and rear elements
• Move all of the elements down when space at the back runs out
• One Analogy: A waiting line in which the server moves (until space runs out)
• Another Analogy: A clock in which the ticks are on a line, not a circle

cppexamples/arrayqueue/moving/Queue.h

        #ifndef edu_jmu_cs_Queue_h
#define edu_jmu_cs_Queue_h

const int maxqueue = 10;

/**
 * A Queue (FIFO list) class.
 *
 * @author Prof. David Bernstein, James Madison University
 */
class Queue {
 public:
  /**
   * Default constructor
   */
  Queue();

  /**
   * Remove and return an element from the front of the queue
   *
   * @return The front element
   */
  int dequeue(void);

  /**
   * Append an element onto the end of the queue
   *
   * @param item   The element to append
   */
  void enqueue(int item);

  /**
   * Is this Queue empty?
   *
   * @return true if the queue is empty and false otherwise
   */
  bool isEmpty(void);

 private:
  int count, front, rear;

  // The array containing the items
  int entry[maxqueue];
};

#endif
        

cppexamples/arrayqueue/moving/Queue.cpp

        #include "Queue.h"
/**
 *
 * This implementation uses an array and a front and rear
 * pointer.  When the rear pointer reaches the maximum value, the
 * contents are moved down (if space permits).
 */

Queue::Queue() {
  rear = 0;
  front = 0;

  count = 0;  // What do you think about this?
}

int Queue::dequeue(void) {
  int item;

  if (count <= 0) {
    item = -1;
  } else {
    item = entry[front];

    count--;
    front++;
  }
  return item;
}

void Queue::enqueue(int item) {
  int i;

  if (count < maxqueue) {
    entry[rear] = item;
    count++;
    rear++;

    if ((rear == maxqueue) && (front > 0)) {
      for (i = 0; i < count; i++)
        entry[i] = entry[front + i];
      front = 0;
      rear = count;
    }
  }
}

bool Queue::isEmpty(void) {
  bool result;

  if (count == 0)
    result = true;
  else
    result = false;

  return result;
}

        

• Keep a "pointer" to the front and rear elements
• Have the "pointers" wrap around
• An Analogy: A circular waiting line in which the server moves

cppexamples/arrayqueue/circular/Queue.h

        #ifndef edu_jmu_cs_Queue_h
#define edu_jmu_cs_Queue_h

const int maxqueue = 10;

/**
 * A Queue (FIFO list) class.
 *
 * @author Prof. David Bernstein, James Madison University
 */
class Queue {
 public:
  /**
   * Default constructor.
   */
  Queue();

  /**
   * Remove and return an element from the front of the queue.
   *
   * @return The front element
   */
  int dequeue(void);

  /**
   * Append an element onto the end of the queue.
   *
   * @param item   The element to append
   */
  void enqueue(int item);

  /**
   * Is this Queue empty?
   *
   * @return true if the queue is empty and false otherwise
   */
  bool isEmpty(void);

 private:
  int count, front, rear;

  // The array containing the items
  int entry[maxqueue];
};

#endif
        

cppexamples/arrayqueue/circular/Queue.cpp

        #include "Queue.h"

/**
 * This implementation uses "circular" array.
 */

Queue::Queue() {
  rear = maxqueue - 1;
  front = 0;

  count = 0;  // What do you think about this?
}

int Queue::dequeue(void) {
  int item;

  if (count <= 0) {
    item = -1;
  } else {
    item = entry[front];

    count--;
    front = ((front + 1) == maxqueue) ? 0 : (front + 1);
  }

  return item;
}

void Queue::enqueue(int item) {
  if (count < maxqueue) {
    count++;

    rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1);
    // Another way:
    //
    //   if ((rear+1) == maxqueue) rear = 0;
    //   else                      rear++;
    //
    // A third way:
    //
    //   rear = ((rear + 1) % maxqueue);

    entry[rear] = item;
  }
}

bool Queue::isEmpty(void) {
  return (count == 0);  // Understand?
}