37. Queues

• elementary data types

  integer

  real

  boolean

  char
• composite data types

  string

  array

  list
• abstract data types

  queues

  stacks

  trees

  graphs
• ADT

  a logical description of how the data is viewed and the operations that can be performed on it, but how this is done is not necessarily known to the user.

  
  

  it's up to the programmer who creates the data structure to decide how to implement it, and it may be built into the programming language. This is a good example of data abstraction. by providing this level of abstraction we are creating an encapsulation around the data.

  
  

  + can easily be shown in graphical form.

  + its not hard to understand how to perform operations such as adding, deleting, or counting elements in each structure.
• information hiding

  is a programming concept that protects data from direct modification by other parts of the program.
• queue

  is a First In First Out (FIFO) data structure. new elements may only be added to the end of a queue, and elements may only be retrieved from the front of a queue.
• the size of the queue depends on...

  the number of items in it e.g. queues at traffic lights or at a supermarket check out.
• encapsulation

  bundling together of data and methods into one unit.
• queues applications

  output waiting to be printed is commonly stored in a queue on a disk. in a room full of networked computers, several people may send work to be printed at more or less the same time. by putting the output into a queue on a disk, the output is printed on a first come, first served basis as soon as the printer is free.

  
  

  characters typed at a keyboard are held in a queue in a keyboard buffer.

  
  

  stimulation program is one which attempts to model a real-situation e.g. check-outs in a supermarket store.
• 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 queue is full.
• dynamic data structure


  refers to the collection of data in memory that has the ability to grow or shrink in size. it does this with the support of the heap.
• the heap


  a portion of memory from which space is automatically allocated or deallocated as required.
• dynamic data structure advantages

  + very useful for implementing data structures such as queues when the maximum size of the data structure is not known in advance.

  + queues can be given random maximum to avoid causing overflow, but it is not necessary to allocate space in advance.
• static data structure

  such as a static array is fixed in size, and cannot increase in size or free up memory while the program is running.
• static data structure advantages

  + an array is suitable for storing a fixed number of items such as the months of the year, monthly sales or average monthly temperatures.

  + no pointers or other data about the structure need to be stored, in contrast to a dynamic data structure.
• static data structure disadvantages

  + using an array to implement a dynamic data structure such as a queue is that the size of the array has to be decided in advance by the programmer, and if the number of items added fills up the array, then no more can be added, regardless of how much free space there is in memory.

  + memory which has been allocated to the array cannot be reallocated even if most of it is unused.
• Implementing a linear queue in an array or list

  • as items leave the queue, all of the other items move up one space so that the front of the queue is always the first element of the structure.
  • a linear queue can be implemented with pointers to the front and rear of the queue. needs an integer holding the size of the array (the maximum size of the queue) and needs a variable giving the number of items currently in the queue.
• however as many items are added to and deleted from the queue, space is created at the front of the queue which cannot be filled, and items are added until rear pointer points to the last element of the data structure.
• circular queue

  one way of overcoming the limitations of implementing a queue as linear queue is to use a circular queue instead, so that when the array fills up and the rear pointer points to the last element of the array, it will be made to point to the first element , when the next person joins the queue. assuming the element is empty.
• circular queue disadvantage

  this solution requires some extra effort on the part of the programmer and is less flexible than a dynamic data structure if the maximum number of items is not known in advance.
• priority queues

  acts like a queue in that items are dequeued by removing them from the front of the queue.

  however, the logical order of the items within the queue is determined by their priority, with the highest priority items at the front of the queue and the lowest priority items at the back of the queue. it is therefore possible that a new item joins the queue at the front, rather than at the rear.