Backnotes

Queues

Abstract Data Types –

Abstract data types are created by programmers instead of being written into the code, to provide explanations and understanding to their code processes.

Queues –

  • First in, First Out data structure, meaning that new data can only be added to the end of the queue, and data can only be retrieved from the start of the queue.
  • Operations can be performed on queues such as:
    • enQueue(item) – adds an item to the end of the queue.
    • deQueue() – retrieves the first item from the start.
    • isEmpty() – checks if empty.
    • isFull() – checks if full.

Dynamic Data Structures –

  • collection of data in memory that has the ability to grow or shrink in size. It does this with the “heap”, a portion of memory from which space is automatically allocated, or deallocated, as required.
  • Dynamic structures may cause overflow if it exceeds the maximum memory limit, which can cause programs to crash, although arbitrary maximums can be used to prevent memory overflow.
  • Useful for implementing data structures such as queues when the maximum size of the data structure is not known in advance.

Static Data Structures –

  • Fixed in size.
  • Size of the array must be decided in advance, removing dynamic capabilities that many modern programs rely on to handle user interactions.

Linear Queue –

  • Implemented so that every time an item leaves the queue, every item moves towards the front so that the first item is always index 0.
  • Implemented with pointers to the start and end of the array.

Circular Queue –

  • To overcome the limitations of static data types, a circular queue can be used, where the items will overwrite old used items when the capacity is filled.
  • When the queue fills up, and the end pointer pints to the last element of the array, it will be made to point to the first element of the array, where the next element is added, assuming this element is empty.

Priority Queue –

  • Acts like a queue, with new items added to the bottom, and items retrieved from the top, however items are ordered by priority, so the order of a queue when a new item is added can change each time.
  • Useful for systems where some tasks need to be completed with a higher degree of urgency than others.