Chapter 14, Problem 2TQ

Program Plan Intro

Queue:

• This is the abstract data type in which access of data is made at both the ends.
• The data is inserted at one end or removed at the other end.
• So, the first item inserted at one end can be retrieved first at the other end. This mechanism is referred to as first-in-first-out (FIFO).
• Insertion and deletion are the common operations of a queue.
  • Inserting an item into the queue is called “Enqueue”.
  • Removing an item from the queue is called “Dequeue”.
• Diagrammatic representation of enqueue operation:

In the above diagram,

• After inserting the item “1” to the empty queue, the “front” and the “rear” pointers point to this first item.
• After inserting the item “9”, the “rear” pointer moves from the item “1” to the item “9”.
• After inserting the item “3”, the “rear” pointer moves from the item “9” to the item “3” and during insertion, the “front” pointer points only to the first item.

Priority queue:

• If the items in the queue are assigned with a priority, then it is called priority queue.
• When inserting an item into the priority queue, the item is added with the priority.
• When removing an item from the priority queue, the item with higher priority is first removed. Then, based on the priority, the other items are removed.
• The maximum number or the minimum number can be deleted by using deletemaximum() or deleteminimum() function.
  • Deletemaximum() is a function which deletes the number which is having the highest priority.
  • Deleteminimum() is a function which deletes the number which is having the lowest priority.