Queue

• Queue


  A data structure where elements are added at one end (the rear) and removed from the other end (the front)

  
• Queues


  • Elements are first-in, first-out (FIFO)
  • Elements may be added at any time, but only the element which has been in the queue the longest may be removed

  
• Basic queue operations


  • Create an empty queue (initializeQueue)
  • Destroy a queue
  • Determine whether a queue is empty (isEmptyQueue)
  • Determine whether a queue is full (isFullQueue)
  • Add a new element to the rear of the queue (enqueue) (addQueue)
  • Removes the front element from the queue (dequeue) (deleteQueue)
  • Returns the front, that is, the first element of the queue (front)
  • Returns the last element of the queue (back)

  
• Implementing a queue as an array

  1. Array to store queue elements

  2. Variable to represent the front (queueFront)

  3. Variable to represent the back (queueRear)

  4. Variable to specify the maximum size of the queue (maxQueueSize)

  
• queueFront


  Indicates the index of the array position preceding the first element of the queue

  
• queueRear


  Indicates the index of the last element in the queue

  
• To add an element to the queue

  • Advance queueRear to the next array position
  • Add the element to the position that queueRear is pointing to

  
• To delete an element from the queue

  • Retrieve the element that queueFront is pointing to
  • Advance queueFront to the next element of the queue

  
• The naïve implementation of queues as arrays has a problem where the queue appears full even though it has only a few elements
• Solutions to the problem of naïve queue implementation as arrays

  1. Upon queue overflow to the rear, check value of queueFront and if room in front, slide all queue elements toward first array position

  2. Assume that the array is circular, advance the queue index queueFront (to delete an item), advance the queue index queueRear (to insert an item)

  
• Implementing queues as circular arrays

  Advance the queue index queueRear

  queueRear = (queueRear + 1) % maxQueueSize

  
• The queue is full if queueRear + 1 == queueFront

  
• Detecting empty queue and full queue conditions

  1. Use a variable count to count the number of items in the queue

  2. Let queueFront indicate the index of the array position preceding the first element of the queue, rather than the index of the actual first element itself

  
• Priority queues


  Customers (jobs) with higher priority are pushed to the front of the queue
• Priority queues relax the FIFO rule to allow items with higher priority to be processed first
• STL class priority_queue


  Provides a container class to implement priority queues in a program
• The STL class priority_queue allows specifying the priority criteria for the queue elements, either by using the default less-than operator (<) or by defining a custom comparison function