Data Structures - Queue ADT

<< Previous

Next >>





  • Queue is a data structure in which insertion is done in one end (rear) whereas deletion of an element can be done in another end (front).
  • It support two operations that are
    • ENQUEUE - insert an element at the end of list-Rear end
    • DEQUEUE- delete an element from the front of the list-Front end
  • It follows the principles of FIFO (First in First out).
  • For example: Theater ticket counter, Train ticket counter, provide the services for computer system such as CPU task scheduling, Printer, Interrupts handling etc.
Fig 1.Queue Model

Implementation of Queue

Queue is implemented by either an array or the linked list. Both implementation give O(1) running time for all operations. For array implementation, we can keep an array, Queue[], positions(Front and Rear) and queue size which keeps track of number of elements in the queue. To Enqueue an new element X, we need to increase the size and increment the Rear position,then set Queue[rear]=X. To Dequeue an element, we need to decrease the size and increment the Front position, then set the return value to Queue[front]=X. Whenever the front or rear reaches to the end of the array ,it is wrapping back to the beginning. This is referred to as circular array implementation.

Basic Operations

Queue is used for the following two basic operations:

  • enqueue(): To add new data into the queue
  • dequeue(): To remove data from queue

Enqueue() Operation

Enqueue is used to insert a new data into the queue. To enqueue of new element X, first check whether the queue is full or not. If the queue is full ,generate the overflow error message otherwise increase the size of the queue and rear value and then set queue[rear]=X.


Implementation of enqueue:
void enqueue(int data)
      {
            if(size==MAXVALUE))
                cout<<"The Queue is full";
            else
            {
                Queue[++rear]=data;
                size++;
                cout<<"data is inserted";
             }
       }

Dequeue() Operation

This operation is used to remove a data from the queue. To dequeue of element X, first check whether the queue is empty or not. If the queue is empty, generate the underflow error message. If the queue is not empty, access the value of Queue[front] and then increase the front value and decrease the size of the queue.


Implementation of dequeue():
void dequeue()
      { int data;
       	if(size==0)
          cout<<"The queue is empty";
        else
        {
          data = Queue[front];
          front=front+1;
          size--;
          cout<<"The return value is"<< data;
      	 }
      }


<< Previous

Next >>




Learn C Progamming

Krivalar.com © 2017