Queues

• Share on Twitter
• Share on Facebook
• Share on StumbleUpon
• Share on Delicious
• Share on Digg
• Share This!

• Queues
  • Introduction
  • Representation
  • Operations
  • Implementation
    • Simple queue
    • With front always at zero
    • Linked queue
    • Dequeue
    • Priority Queues
      • Max Priority
      • Min Priority

Queues

A queue is a FIFO structure – First In First Out.  A queue is a data structure in which insertion of a new element is done at the rear end and deletion of an element is done at the front end of the queue.  Hence, it is different from the stack, since it uses both the ends to perform insertion and deletion rather than using only one end for these operations.  The operations on queue are similar to those of stack.  Enqueue operation represents insertion of a new element in the queue and Dequeue operation represents deletion of an element from the queue.

Representation:

Queue may be represented using arrays or linked list.  Array representation involves keeping track of two positions via. subscript for front and rear, whereas linked list involves two pointers, one positioned at the front end of the queue and the other positioned at the rear end of the queue.

i)  Array representation of queue:  Queues may be representated using arrays as follows:

 
• Program to implement a Queue using Array with front always at zero
• Program to implement a Queue using Array by incrementing front as well as rear

ii) Linked list implementation of queue:  Linked list may also be used to represent a queue as follows:

• Program to implement Linear Queues using Linked List (POST SOON)
• Program to implement Linear Queues using Linked list using global front and rear pointers (POST SOON)

Double Ended Queues (Dequeue):

A double ended queue allows fast insertion and deletion at the beginning as well as at the end of the queue.  It supports all the operations applicable for an ordinary queue.  But, enqueue may be done at front end too and dequeue may be done at rear end.

• Program to implement Dequeue (Double Ended Queues) using Arrays with front always at zero

Priority Queues:

In a priority queue, the elements are dequeued according to their priority and their current queue position.  Priority may be assigned to elements such that dequeue operation may be based on priority.  Thus, it is not necessary in a priority queue, that the element at the front position is the candidate for deletion.  Priorities may be assigned such that higher priorities may be associated with lower numbers and lower priorities may be associated with higher numbers or vice-versa.   The elements may be arranged at the time of entry or using some ordering function.  Two versions of priority queues may be implemented in general.  First one is Max priority queue and the second one is Min priority queue.

i)  Max Priority Queue:

In a max priority queue, each element is assigned a priority.  The element to be dequeued is the element with the max priority.  The elements are extracted in the descending order of priority.  The program to implement max priority queue is as follows-

• Program to implement MAX Priority Queue(POST SOON)

ii) Min Priority Queue:

In a min priority queue, each element is assigned a priority.  The element to be dequeued is the element with the min priority.  The elements are extracted in the ascending order of priority.  The program to implement min priority queue is as follows-

• Program to implement MIN Priority Queue(POST SOON)