Queue

Queue

• Linear data structure
• First in first out(FIFO)
• rear: inserted at one end
• front: removed from the other end

Operations in an Queue

• En-Queue : add items on the *Rear end
• De-Queue : remove items from the front end
  

  

Applications of Queue

• checkout line, printer/keyboard/mouse queue, Airport take-off,
  Operating system(Job scheduling, Multi-programming)
• Different types of scheduling algorthms : Round Robin

Using arrays (static implementation)

 

Using pointer (dynamic implementation)

Queue Operations

Algorithm : Enqueue

ENQUEUE (QUEUE, REAR, FRONT, ITEM)

Algorithm : Dequeue

DEQUEUE (QUEUE, REAR, FRONT, ITEM)

 

pointer implementation of Queue

Recommended Functions

• Queue creates a new, empty queue
  :parameters(x), returns(x)
• enqueue(item) adds a new item to rear
  :item(need), returns(x)
• dequeue() removes front item
  :parameters(x),returns(x),item(x)
• isEmpty() test if queue is empty
  :parameters(x), returns->boolean
• size returns number of items in the queue
  :parameters(x), returns->integer

Four Types of Queues

• simple queue, circular queue, priority queue, de-queue(Double Ended Queue;x)

Simple Queue

• Insertion: rear
• Deletion : front
  

  

Circular Queue

• all nodes are treated as a circle
• last node follows the first node
  

  

Array Implementation

logical circularity of Queue

 

Drawbacks of Circular Queue

• Boundary case problem : difficult to distinguish full, empty queues
• necessary
  before insertion, check overflow
  before deletion, check underflow
• Condition to check FULL Circular Queue
  If (( front == MAX-1) || ( front ==0 && rear == MAX - 1))
• Condition to check EMPTY Circular Queue
  if (( front == MAX-1) || ( front ==0 && rear == MAX - 1))
• To solve the drawback of circular Queue
  : count variable to hold the current position

Circular Queue using count

 

Insertion Operation

Deletion Operation

Priority Queue

• each item have some pre-defined priotiry.
• element can be inserted or removed from any position depending upon their priority
  

  

• FIFO x
• OPERATION
  -InsertWithPriority : insert an item to the queue with associated priority
  -GetNext : remove the element from the queue which has highest priority.
  PopElement() or GetMaximum
  -PeekAtNext(optional) : Get the item with highest prioity without removing it
• every item has a priority associated with it
• high priority > low priority (dequeue)
• same priority -> order
  -typical operations
  insert(item, priority) : inserts an item with given priority
  getHighestPriority() : returns the highest priority item
  deleteHighestPriority() : Removes the highest priority item

Implementing Priority Queue

• insert() adding an item at end of array/ O(1) time
• getHighesPriority() Linearly search the highest priority item in array./ O(n) time
• deleteHighestPriority() First linearly search an item, them remove the item by moving all subsequent items one position back
• using linked list, time complextiy of all opearations remains same as array
• the advantage with linked list is deleteHighestPriority() can be more efficient as we don't have to move items

Some Applications of Queue

• modeling and analysis of computer networks
• cpu scheduling
• Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree.
• All queue applications where priority is involved
  -Heap Sort