Queues

• Abstract data type


  One that is created by the programmer, rather than defined within the programming language. They include structures such as queues, stacks, trees and graphs.
• Abstract data type (ADT)

  • A logical description of how the data is structured and the operations that can be performed on it, but how this is to be done is not necessarily known to the user
• Data abstraction


  Providing a level of abstraction and creating an encapsulation around the data, hiding the details of implementation from the user
• Queue


  A First In First Out (FIFO) data structure where elements may only be added to the end and retrieved from the front
• Uses of queues


  • Output waiting to be printed is commonly stored in a queue on disk
  • Characters typed at a keyboard are held in a queue in a keyboard buffer
  • Simulation problems to model real-life situations like customers arriving at random times at supermarket checkouts
• The size of the queue depends on the number of items in it, just like a queue at traffic lights or at a supermarket checkout
• Queue


  An ordered collection of items which are added at the rear and removed from the front
• enQueue(item)


  Add a new item to the rear of the queue
• deQueue()


  Remove the front item from the queue and return it
• isEmpty()


  Test to see whether the queue is empty
• isFull()


  Test to see whether the queue is full
• Queue contents


  • Jason
  • Mily
  • Bob
  • Adam
• When an item leaves the queue, the front pointer is made to point to the next item, the elements do not move
• When an item joins the queue, the rear pointer points to the new item
• Think of a queue like a doctors surgery - people leave and join the queue, but no one moves chairs
• Dynamic data structure


  A collection of data in memory that has the ability to grow or shrink in size. It uses the heap, a portion of memory from which space is automatically allocated or de-allocated as required.
• Static data structure


  A data structure that is fixed in size and cannot increase in size or free up memory while the program is running, such as an array.
• Priority queue


  A queue where the logical order of items is determined by their priority, with the highest priority items at the front and the lowest priority items at the back
• How a priority queue works

  1. Items are dequeued by removing them from the front of the queue

  2. New items can join the queue at the front rather than the rear, depending on their priority
• Implementing a priority queue

  Check the priority of each item in the queue, starting at the rear and moving it along one place until an item with the same or lower priority is found, at which point the new item can be inserted
• An operating system might schedule jobs in order of priority, or a printer may give shorter print jobs priority over longer ones