The following source codes are used in this chapter. A FIFO (first-in, first-out) queue is a data structure that comprises two basic operations: insert (put) a new item, and remove (get) the item that was least recently inserted.

Queue using Array

1. Main function using Queue class

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 8: Queues

// Queue
// using array

#include "queue_array.h"

int main() {
  Queue<char> q(6);
  char s[] = "Queues;", ch;
  int i=0;

  while(*(s+i) && q.insert(*(s+i)))
     cout << "queue <-- " << *(s+i++) << endl;

/*
  while(*(s+i) && !q.full()) {
     q.insert(*(s+i));
     cout << "queue <-- " << *(s+i++) << endl;
  }
*/

  while(q.remove(ch))
    cout << " queue --> " << ch << endl;
}

2. Header file: queue_array.h

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 8: Queues

// Queue using array
// File name: queue_array.h

#include <iostream>
using namespace std;

template <class Type>
class Queue {
   Type * queue;
   int front, back, MaxSize;
public:
   Queue(int MSize) : MaxSize(MSize) {
      queue = new Type[MaxSize];
      front = back = 0;
   }
   ~Queue() {
      delete [] queue;
   }
   bool insert(Type item);
   bool remove(Type& item);
   bool empty();
   bool full();
};
template <class Type> bool Queue<Type>::insert(Type item) {
   if(full()) {
      cout << "Queue is full\n";
      return false;
   }
   else {
      back = (++back) % MaxSize;
      queue[back] = item;
      return true;
   }
}
template <class Type> bool Queue<Type>::remove(Type& item) {
   if(empty()) {
      cout << "Queue is empty\n";
      return false;
   }
   else {
      front = (++front) % MaxSize;
      item = queue[front];
      return true;
   }
}
template <class Type> bool Queue<Type>::empty() {
   if(front == back) return true;
   else return false;
}
template <class Type> bool Queue<Type>::full() {
   if(front == (back+1)%MaxSize) return true;
   else return false;
}

Queue using Linked List

1. Main function using Queue class

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 8: Queues

// Queue
// using list

#include "queue_list.h"

int main() {
  Queue<char> q;
  char s[] = "Queues fre;", ch;
  int i=0;

  while(*(s+i) && q.insert(*(s+i)))
     cout << "queue <-- " << *(s+i++) << endl;

  while(q.remove(ch))
    cout << " queue --> " << ch << endl;
}

2. Header file: queue_list.h

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 8: Queues

// Queue using list
// File name: queue_list.h

#include <iostream>
using namespace std;

template <class Type>
class Queue {
   struct Node {
      Type data; Node *link;
      Node(Type d) : data(d), link(NULL) {}
   };
   Node *front, *back;
public:
   Queue() {
      front = back = NULL;
   }
   ~Queue();
   bool insert(Type item);
   bool remove(Type& item);
   bool empty();
};
template <class Type> Queue<Type>::~Queue() {
  while(front) {
     back = front;
     front = front->link;
     delete back;
  }
}
template <class Type> bool Queue<Type>::insert(Type item) {
   Node *new_node;
   new_node = new Node(item);
   if(new_node) {
      if(empty()) front = back = new_node;
      else {
	 back->link = new_node;
	 back = back->link;
      }
      return true;
   }
   else return false;
}

template <class Type> bool Queue<Type>::remove(Type& item) {
   if(empty()) {
      cout << "Queue is empty\n";
      return false;
   }
   else {
      Node *temp = front;
      item = front->data;
      if(front == back) front = back = NULL;
      else front = front->link;
      delete temp;
      return true;
   }
}
template <class Type> bool Queue<Type>::empty() {
   if(!front) return true;
   else return false;
}