Queue–An Introduction

“Queue of things!! A queue to buy tickets!!.. Its the same queue we talk about in computers as well.. The first person in the queue gets the chance to get the ticket first!!”

Metaphor

   The metaphor is as same as buying tickets for a movie in a theatre by standing in a queue. Only the first person in the queue gets the ticket first. This approach is called First-in, First-out in short (FIFO). Stack data structure is that’s why called as LIFO (Last-in, First out) and Queue is FIFO type.

  What is the use of such things in a computer? The same use like what we get in a real life queues. Order the items based on the order in which they are processed. In a scheduler, if a job is scheduled, it means it is put in a queue. The job which came first is allowed to be executed by a scheduler. In olden times, they just used a simple queues. But with advancement in mathematics and computer memory, very good scheduling algorithms came which never makes the CPU idle.

  Stack & Queues are the very basic data structures used in computers in almost all the algorithms.

Concept

  What would a queue need to be implemented? As usual, a dynamic or static structure, array or linked list.

The operations:

  - Enqueue or insertion

  - Dequeue or deletion

Queues have a front and a back. Insertion happens at the front. Deletion happens at the back. As you rotate inside if its a static array, like we did in all in-place algorithm. We must create a hole in this algorithm as well!!

Rotations also needs a hole!!.

i.e, if there is an Array like A[1…n], you can use only up to n-1. So, in an array like A[0..4], you can use only 0,1,2,3 indexes. The one index left is the hole index.

Code

Some important confusions:

• The first confusion is the index!!. You need both front and back
• When Front == back, queue is empty!!. This is a invariant btw. :D
• When front = back + 1 or front is zero and back > queue size, queue is full
• Note that we never fill more than index 3. Even though we have an array of size 5 running from 0..4
• The initial hole created at index 4, keeps on moving.. Since we maintain front = back+1 for a full condition!! THIS IS VERY VERY IMPORTANT
• If a character is given using “”, its a const char*.
• If a member function needs to be marked as const, it should not do any assignment operations using the argument!!! So, dequeue cannot be a const function

 

   1:   

   2:  const int QSIZE=5;

   3:   

   4:  template<class T>

   5:  class Queue

   6:  {

   7:      T arr[QSIZE];

   8:      int front;

   9:      int back;

  10:   

  11:  public:

  12:      Queue()

  13:      {

  14:          front=0;

  15:          back=0;

  16:      }

  17:   

  18:      bool enqueue(const T val)

  19:      {

  20:          if(isFull()) return false;

  21:   

  22:          arr[back] = val;

  23:          if(back == QSIZE-1)

  24:              back = 0;

  25:          else

  26:              back++;

  27:   

  28:          return true;

  29:      }

  30:   

  31:      // cannot mark this fn as const

  32:      bool dequeue(T& val)

  33:      {

  34:          if(isEmpty()) 

  35:              return false;

  36:   

  37:          val = arr[front];

  38:          arr[front] = "";

  39:          if(front == QSIZE-1)

  40:              front = 0;

  41:          else

  42:              front++;

  43:   

  44:          return true;

  45:      }

  46:   

  47:      bool isEmpty() const { return (front == back); }

  48:   

  49:      bool isFull() const { return (front == back + 1 || (front ==0 && back==QSIZE-1)); }

  50:  };

  51:   

  52:  void main()

  53:  {

  54:      Queue<char*> names;

  55:      // Note that all are const char*

  56:      names.enqueue("Jack");

  57:      names.enqueue("Muthu");

  58:      names.enqueue("Murugan");

  59:      names.enqueue("Kumar");

  60:      names.enqueue("Vinay");

  61:      names.enqueue("Purva");

  62:   

  63:      char* toppers="";

  64:      // remove jack, muthu

  65:      for(int i=0; i<2;i++)

  66:          names.dequeue(toppers);

  67:   

  68:      // enqueue rowdi

  69:      // eventhough they go at top index

  70:      // they are not at front :)

  71:      for(int i=0;i<4;i++) 

  72:          names.enqueue("Rowdis");

  73:   

  74:      // Now, murugan & kumar 

  75:      // Rowdis cannot do anything!!

  76:      for(int i=0; i<2;i++)

  77:          names.dequeue(toppers);

  78:   

  79:      // Polician join Rowdies now

  80:      // here too only after Rowdies, Politicians :)

  81:      for(int i=0;i<4;i++) 

  82:          names.enqueue("Politician");

  83:   

  84:  }