Data Structures: Introduction to Queues

Queue is a linear data structure in which data can be added to one end and retrieved from the other. Just like the queue of the real world, the data that goes first into the queue is the first one to be retrieved. That is why queues are sometimes called as First-In-First-Out data structure.

In case of queues, we saw that data is inserted both from one end but in case of Queues; data is added to one end (known as REAR) and retrieved from the other end (known as FRONT).

The data first added is the first one to be retrieved while in case of queues the data last added is the first one to be retrieved.

A few points regarding Queues:

1. Queues: It is a linear data structure; linked lists and arrays can represent it. Although representing queues with arrays have its shortcomings but due to simplicity, we will be representing queues with arrays in this article.

2. Rear: A variable stores the index number in the array at which the new data will be added (in the queue).

3. Front: It is a variable storing the index number in the array where the data will be retrieved.

Let us have look at the process of adding and retrieving data in the queue with the help of an example.

Suppose we have a queue represented by an array queue [10], which is empty to start with. The values of front and rear variable upon different actions are mentioned in {}.

queue [10]=EMPTY {front=-1, rear=0}

add (5)

Now, queue [10] = 5 {front=0, rear=1}

add (10)

Now, queue [10] = 5, 10 {front=0, rear=2}

retrieve () [It returns 5]

Now, queue [10] = 10 {front=1, rear=2}

retrieve () [now it returns 10]

Now, queue [10] is again empty {front=-1, rear=-1}

In this way, a queue like a stack, can grow and shrink over time.

Now have a look at the following example program that illustrates all this stuff:

  // -- A Queue Class in C++ --
  // example program in C++ to
  // illustrate queues represented
  // by arrays
  #include<iostream.h>

  // macro to hold the max
  // number of elements
  // in the queue
  #define MAX 10

  // queue class
  class queue
  {
   int arr[MAX];
   int front, rear;
 
  public:

   void add(int);
   int retrieve(void);
   queue();
  };
  // queue class ends

  // member functions
  queue::queue()  
  {
   // initialize index
   // variables
   front=-1;
   rear=0;
  }

  void queue::add(int data)
  {
   if(rear==MAX-1)
   {
    cout<<"QUEUE FULL!";
    return;
   }

   arr[rear]=data;
   // increase index
   // variable
   rear++;

   if(front=-1)
   front=0;
  }

  int queue::retrieve()
  {
   int data;
 
   if(front==-1)
   {
    cout<<"QUEUE EMPTY!";
    return NULL;
   }

   data=arr[front];
   arr[front]=0;
  
   // if both index variables
   // point to the same location
   // then start afresh
   if(front==rear-1)
   {
    front=-1;
    rear=0;
   }
   else
    front++;

   return data;
  }
  // member functions ends

  void main(void)
  {
   queue obj;
   int ch;
   int num;

   while(ch!=3)
   {
    cout<<"1> ADD";
    cout<<"\n2> RETRIVE";
    cout<<"\n3> QUIT\n";

    cin>>ch;

    switch(ch)
    {
     case 1:
     cout<<"enter element:";
     cin>>num;

     obj.add(num);
     break;

     case 2:
     cout<<"\n\nRetrieved: ";
     cout<<obj.retrieve();
     cout<<"\n\n";
     break;
    }
   }
  }

Good-Bye

Please do check back for updates!

Related Articles:

• Data Structures: Introduction to Stacks