Queues

Introduction

A queue has the property of first in, first out (FIFO). The abstract data type that supports the FIFO principle and provides useful functions is the "Queue" class. Its operations and structure is similar to the now familiar "Stack" ADT except the LIFO paradigm of a stack is replaced by FIFO for the queue. Thinking back to our discussion on stacks, we remember that we can't (and shouldn't) know ahead of time what kind of object our queue will store. Once again, if we'd like to declare a queue named Q for storing chars, we'd type:

Queue<char> Q;

Below is the ADT for type Queue (once again we're giving you a more modern ADT and the "traditional" ADT), a class implementing the ADT that you can use for Queues holding whatever type you want, and a small example program using the Queue implementation. The important thing about a queue is that it works like a regular old-fashioned line - the one who's been waiting longest is the next one to come out. "enqueue" adds an element to the back of a queue, "dequeue" pulls an element off the front of a queue. "getFront" or "peek" allow you to look at the front element without actually removing it, which you need because once something's pulled off the front, it must go to the back of the line if you're going to put it back into the queue.

Queue();
~Queue();
bool isEmpty() const;
void push(const DataType &val);
void pop();
DataType getFront() const;
    

Queue();
~Queue();
bool isEmpty() const;
void enqueue(const DataType &val);
DataType dequeue();
DataType peek() const;
      

#include "Queue.h"
#include <iostream>
using namespace std;

int main(){
  // Read values and store in Q
  Queue<double> Q;
  int n = 0;
  for(double x; cin >> x; n++)
    Q.push(x);

  // Sum values stored in Q
  double sum = 0;
  while(!Q.isEmpty()) {
    sum += Q.getFront();
    Q.pop();
  }

  // Print average
  cout << sum/n << endl;
  return 0;
}

#include "TradQueue.h"
#include <iostream>
using namespace std;

int main() {
  // Read values and store in Q
  Queue<double> Q;
  int n = 0;
  for(double x; cin >> x; n++)
    Q.enqueue(x);

  // Sum values stored in Q
  double sum = 0;
  while(!Q.isEmpty()) {
    sum += Q.dequeue();
  }

  // Print average
  cout << sum/n << endl;
  return 0;
}

There are other functions we could include in the interface, but these should suffice. With stacks, if we wanted to see just the first item in the stack we simply did a pop followed by a push. To do the same with queues, we'd have to dequeue the entire queue and then enqueue all items again! peek is included as an additional function to the traditional queue; otherwise, we wouldn't have a cheap method of looking at the first item in a queue.