1.4.2 Data structures

• A stack is an abstract data structure, consisting of a series of data items. New item is added through push and an item is removed through pop. A LIFO structure: most recently added item will be the one that is removed. An item cannot be removed from an empty stack or added to a full stack.
• Uses of a stack:

  Low level - calling stack for passing parameters and returning the address to functions, syntax parsing.

  High level - reverse a list, back and forward browser buttons, undo/redo
• Stack pointer indicates where the next item will be added.
• Pop decreases the stack pointer so that the new value would override the existing one - item in pointer is returned.
• In an exam: stacks are a static array - declared with a fixed size with changing contents but elements do not change.
• Stack pointer starts at 0 when empty.

  Stack pointer = array size when full
• When creating a stack:

  1. Initialize stack
  2. Set pointer to 0
  3. Declare array of size 'MAXSIZE'
• Queue:

  First in, first out data structure

  Series of data items: abstract data structure

  A new item is added to the rear of the queue, ENQUEUE

  An item is removed from the front of the queue, DEQUEUE.

  Order of items is maintained
• Queue uses:

  Low level - maintaining order of processing of jobs (such as a printer queue)

  High level - simulations and games can use queues to model structures e.g customers being served in a shop in retail simulation.
• Front pointer - first item in a queue
• Rear pointer - last item in a queue
• Dequeue:

  1. Increment front pointer
  2. Return item at fp-1
  3. Rear pointer is the same.
• Enqueue:

  1. Add item to queue at rear.
  2. Increment rear pointer by one.
• Tests:

  frontpointer === rearpointer (empty)

  rearpointer === arraysize (full)