ADT : Queue

• Queues : Overview
  • Queue ADT: first in, first out
  • a constructor, which creates and initializes a new (empty) queue
  • an Enqueue operation, which takes a new data item and (as long as the queue is not full) adds it to the end of the queue
  • a dequeue operation, which removes a data item from the front of the queue (as long as the queue is not empty) and returns it
  • a destructor, which deallocates a queue which is no longer needed
  • an isempty operation, which returns true if the queue is empty and false otherwise
  • an isfull operation, which returns true if the queue is full and false otherwise
  • a getsize operation, which returns a count of the number of items currently in the queue
• Pointer-based Queue Interface

  class Queue {
    public:
      // the public interface  
      Queue();               // initializes queue with default maxsize
      Queue(int max);        // initializes queue with specified maxsize
      ~Queue();              // deallocates queue
      void enqueue(QElem& e);// addes e to queue if queue isn't full
      QElem & dequeue(); // removes/returns front queue element 
                          //    if queue isn't empty
      int  getsize();     // returns current count of queue elements
      bool isempty();     // returns true iff queue is empty
      bool isfull();      // returns true iff queue is full
      void printQ();      // prints current queue contents
  
    private:
      // the "inaccessible" implementation details
      struct Node {
        QElem *data;
        Node *prev;
        Node *next;        
      };
      Node *Q;           // a pointer to the front queue element
      int maxQsize;          // the chosen maximum queue size
      int actQsize;          // the current number of elements in queue
  };
  

• Implementation

  #include "pointerq.h"
  
  Queue::Queue()
  {
    Q = new Node;
    maxQsize = DEFAULTMAXSIZE;
    actQsize = 0;
    Q->prev = Q;
    Q->next = Q;
    Q->data = NULL;
  }
  
  Queue::Queue(int max)
  {
    Q = new Node;
    maxQsize = max;
    actQsize = 0;
    Q->prev = Q;
    Q->next = Q;
    Q->data = NULL;
  }
  
  Queue::~Queue()
  {
    Node *temp;
    while (Q->next != Q) {
      Q->next = Q->next->next;
      delet Q->next->prev;
      Q->next->prev = Q;
    }
    delete Q;
    actQsize = 0;
    maxQsize = DEFAULTMAXSIZE;
  }
  
  void Queue::enqueue(QElem & e)
  {
    Node *temp = NULL;
    if (actQsize < maxQsize) {
       temp = new Node;
    }
    if (temp == NULL) {
       throw string("ERROR: queue overflow");
    }
    temp->data = &e;
    temp->prev = Q->prev;
    temp->next = Q;
    Q->prev->next = temp;
    Q->prev = temp;    
    actQsize++;
  }
  
  QElem & Queue::dequeue()
  {
    if (actQsize == 0) {
       throw string("ERROR: queue underflow");
    }
    QElem & e = *(Q->next->data);
    Q->next = Q->next->next;
    delete Q->next->prev;
    Q->next->prev = Q;
    actQsize--;
    return e;
  }
  
  int Queue::getsize()
  {
     return actQsize;
  }
  
  bool Queue::isempty()
  {
     return (ActQsize == 0);
  }
  
  bool Queue::isfull()
  {
     return (actQsize == maxQsize);
  }
  
  void Queue::printQ()
  {
     cout << "The queue has " << actQsize << " of " << MaxQsize;
     cout << " possible elements:" << endl;
     
     Node *temp = Q->next;
     int i = 0
     while (temp != Q) {
         cout << temp->data;
         i++;
         if (((i % 5) == 0) || (i == actQsize))
           cout << endl;
         else cout << " ";
     }
  }
  

• Array Queue Interface

  class Queue {
    public:
      // the public interface  
      Queue();              // initializes queue with default maxsize
      Queue(int max);       // initializes queue with specified maxsize
      ~Queue();             // deallocates queue
      void enqueue(QElem & e);// addes e to queue if queue isn't full
      QElement & dequeue(); // removes/returns front queue element 
                            //    if queue isn't empty
      int  getsize();       // returns current count of queue elements
      bool isempty();       // returns true iff queue is empty
      bool isfull();        // returns true iff queue is full
      void printQ();        // prints current queue contents
  
    private:
      // the "inaccessible" implementation details
      QElem **Q;     // a pointer to the front queue element
      int maxQsize;    // the chosen maximum queue size
      int actQsize;    // the current number of elements in queue
      int front;       // current position of the first element in queue
      int back;        // current position of the last element in queue
  };
  

• Implementation

  #include "arrayq.h"
  
  Queue::Queue()
  {
    Q = new (QElem *)[DEFAULTMAXSIZE];
    maxQsize = DEFAULTMAXSIZE;
    actQsize = 0;
    front = 0;
    back = -1;
  }
  
  Queue::Queue(int max)
  {
    Q = new (QElem *)[max];
    maxQsize = max;
    actQsize = 0;
    front = 0;
    back = -1;
  }
  
  Queue::~Queue()
  {
    delete [] Q;
    front = 0;
    back = -1;
    actQsize = 0;
    maxQsize = 0;
  }
  
  void Queue::enqueue(QElem & e)
  {
     if (actQsize >= maxQsize) {
        throw string("ERROR: queue overflow");
     }
     back++;
     back = back % maxQsize;
     Q[back] = &e;
     actQsize++;
  }
  
  QElem & Queue::dequeue()
  {
     if (actQsize == 0) {
        throw string("ERROR: queue underflow");
     } else {
        QElem & e = *Q[front];
        front++;
        front = front % maxQsize;
        ActQsize--;
        return e;
  }
  
  int Queue::getsize()
  {
     return actQsize;
  }
  
  Boolean Queue::isempty()
  {
     return (actQsize == 0);
  }
  
  Boolean Queue::isfull()
  {
     return (ActQsize == MaxQsize);
  }
  
  void Queue::printQ()
  {
     int index;
     index = front;
     cout << "The queue has " << actQsize << " of " << maxQsize;
     cout << " possible elements:" << endl;
     
     for (int i = 1, index = front; i <= actQsize; i++, index++) {
         index = index % maxQsize;
         cout << *Q[index];
         if (((i % 5) == 0) || (i == actQsize))
            cout << endl;
         else
            cout << " ";
     }
  }