Queue


What is a Queue?


Queue is a linear data structure in which the insertion and deletion operations are performed at two different ends. In a queue data structure, adding and removing of elements are performed at two different positions. The insertion is performed at one end and deletion is performed at other end. In a queue data structure, the insertion operation is performed at a position which is known as 'rear' and the deletion operation is performed at a position which is known as 'front'. In queue data structure, the insertion and deletion operations are performed based on FIFO (First In First Out) principle.


In a queue data structure, the insertion operation is performed using a function called "enQueue()" and deletion operation is performed using a function called "deQueue()".

Queue data structure can be defined as follows...
Queue data structure is a linear data structure in which the operations are performed based on FIFO principle.
A queue can also be defined as
"Queue data structure is a collection of similar data items in which insertion and deletion operations are performed based on FIFO principle".

Example

Queue after inserting 25, 30, 51, 60 and 85.



Operations on a Queue

The following operations are performed on a queue data structure...

  1. enQueue(value) - (To insert an element into the queue)
  2. deQueue() - (To delete an element from the queue)
  3. display() - (To display the elements of the queue)

Queue data structure can be implemented in two ways. They are as follows...

  1. Using Array
  2. Using Linked List

When a queue is implemented using array, that queue can organize only limited number of elements. When a queue is implemented using linked list, that queue can organize unlimited number of elements.

Queue Using Array


A queue data structure can be implemented using one dimensional array. But, queue implemented using array can store only fixed number of data values. The implementation of queue data structure using array is very simple, just define a one dimensional array of specific size and insert or delete the values into that array by using FIFO (First In First Out) principle with the help of variables 'front' and 'rear'. Initially both 'front' and 'rear' are set to -1. Whenever, we want to insert a new value into the queue, increment 'rear' value by one and then insert at that position. Whenever we want to delete a value from the queue, then increment 'front' value by one and then display the value at 'front' position as deleted element.

Queue Operations using Array

Queue data structure using array can be implemented as follows...

Before we implement actual operations, first follow the below steps to create an empty queue.
  • Step 1: Include all the header files which are used in the program and define a constant 'SIZE' with specific value.
  • Step 2: Declare all the user defined functions which are used in queue implementation.
  • Step 3: Create a one dimensional array with above defined SIZE (int queue[SIZE])
  • Step 4: Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -1, rear = -1)
  • Step 5: Then implement main method by displaying menu of operations list and make suitable function calls to perform operation selected by the user on queue.

enQueue(value) - Inserting value into the queue

In a queue data structure, enQueue() is a function used to insert a new element into the queue. In a queue, the new element is always inserted at rear position. The enQueue() function takes one integer value as parameter and inserts that value into the queue. We can use the following steps to insert an element into the queue...
  • Step 1: Check whether queue is FULL. (rear == SIZE-1)
  • Step 2: If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function.
  • Step 3: If it is NOT FULL, then increment rear value by one (rear++) and set queue[rear] = value.

deQueue() - Deleting a value from the Queue

In a queue data structure, deQueue() is a function used to delete an element from the queue. In a queue, the element is always deleted from front position. The deQueue() function does not take any value as parameter. We can use the following steps to delete an element from the queue...
  • Step 1: Check whether queue is EMPTY. (front == rear)
  • Step 2: If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the function.
  • Step 3: If it is NOT EMPTY, then increment the front value by one (front ++). Then display queue[front] as deleted element. Then check whether both front and rear are equal (front == rear), if it TRUE, then set both front and rear to '-1' (front = rear = -1).

display() - Displays the elements of a Queue

We can use the following steps to display the elements of a queue...
  • Step 1: Check whether queue is EMPTY. (front == rear)
  • Step 2: If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
  • Step 3: If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'.
  • Step 3: Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i' value is equal to rear (i <= rear)

Queue using Linked List

The major problem with the queue implemented using array is, It will work for only fixed number of data. That means, the amount of data must be specified in the beginning itself. Queue using array is not suitable when we don't know the size of data which we are going to use. A queue data structure can be implemented using linked list data structure. The queue which is implemented using linked list can work for unlimited number of values. That means, queue using linked list can work for variable size of data (No need to fix the size at beginning of the implementation). The Queue implemented using linked list can organize as many data values as we want.

In linked list implementation of a queue, the last inserted node is always pointed by 'rear' and the first node is always pointed by 'front'.

Example

 

In above example, the last inserted node is 50 and it is pointed by 'rear' and the first inserted node is 10 and it is pointed by 'front'. The order of elements inserted is 10, 15, 22 and 50.

Operations

To implement queue using linked list, we need to set the following things before implementing actual operations.
  • Step 1: Include all the header files which are used in the program. And declare all the user defined functions.
  • Step 2: Define a 'Node' structure with two members data and next.
  • Step 3: Define two Node pointers 'front' and 'rear' and set both to NULL.
  • Step 4: Implement the main method by displaying Menu of list of operations and make suitable function calls in the mainmethod to perform user selected operation.

enQueue(value) - Inserting an element into the Queue

We can use the following steps to insert a new node into the queue...
  • Step 1: Create a newNode with given value and set 'newNode → next' to NULL.
  • Step 2: Check whether queue is Empty (rear == NULL)
  • Step 3: If it is Empty then, set front = newNode and rear = newNode.
  • Step 4: If it is Not Empty then, set rear → next = newNode and rear = newNode.

deQueue() - Deleting an Element from Queue

We can use the following steps to delete a node from the queue...
  • Step 1: Check whether queue is Empty (front == NULL).
  • Step 2: If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate from the function
  • Step 3: If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.
  • Step 4: Then set 'front = front → next' and delete 'temp' (free(temp)).

display() - Displaying the elements of Queue

We can use the following steps to display the elements (nodes) of a queue...
  • Step 1: Check whether queue is Empty (front == NULL).
  • Step 2: If it is Empty then, display 'Queue is Empty!!!' and terminate the function.
  • Step 3: If it is Not Empty then, define a Node pointer 'temp' and initialize with front.
  • Step 4: Display 'temp → data --->' and move it to the next node. Repeat the same until 'temp' reaches to 'rear' (temp → next != NULL).
  • Step 4: Finally! Display 'temp → data ---> NULL'.


No comments: