5.1.4 – 5.1.10 – Abstract Data Structures

5.1.4 – Describe the characteristics of a two-dimensional array

For the most part 2D arrays are very simple.

Where as a 1D array would look something like below

See the source image

A 2D array is accessed exactly the same way however with 2 variables

See the source image

The first value is the Row, the second being the Column

For example with an array called Superhero created with a 5 x 5 matrix

Superhero[3][1] would access the name in the 4th row at the 2nd column which in this case would output…. “Mr Godbold”…… Just sayin!

5.1.5 – Construct algorithms using two-dimensional arrays

5.1.6 – Describe the characteristics and applications of a stack

Stacks store items in a particular order and is a Last In First Out  (LIFO) data type.

You have to remove the item at the top of the stack first (opposite to the queue)

Stacks can be used to reverse the order of a word.

Think of an operating system loading, followed by a program, followed by all a plugin. In order to shut down effectively it would need to close the plugin first, then the program, then the operating system.

5.1.7 Construct algorithms using the access methods of a stack

Say for example if we have a stack titled ‘food’ we could use the following:

Method Description Example
push() Adds or (pushes) an item onto the stack food.push(pizza)
Pop() Removes or (pops) an item from the stack food.pop()
isEmpty() Checks to see if the stack is empty. If food.isEmpty()
then    

Sometimes you can get this. When the stack is NOT EMPTY do …..

Uses of Stacks in Computing

  • The undo function to backtrack.
  • Calling functions recursively
  • Internet History

5.1.8 – Describe the characteristics and applications of a Queue

queue is a first-in first-out (FIFO) abstract data type that is heavily used in computing. Uses for queues involve anything where you want things to happen in the order that they were called, but where the computer can’t keep up to speed.

For example imagine a queue was not used when 100 people used the office printer. People would never know when their work would come, people who printed last may get their work before those who printed first. The first person could be waiting forever!

5.1.9 – Construct algorithms using the access methods of a Queue

If we have a queue titled ‘food’ we can use the following:

Method Description Example
enqueue() Adds an item to the back of the queue food.enqueue(“sausages”)
dequeue() Removes an item from the front of the queue. food.dequeue()
isEmpty() Checks to see if the queue is empty (Returns – True or False) If food.isEmpty()
then

Uses of Queues in Computing

  • Sending Packets in data communication
  • Operating systems in job scheduling
  • When a resource is shared amongst multiple consumers/devices (CPU is a good example)

5.1.10 – Explain the use of arrays as static stacks and queues

The important thing to remember is that the stack or queue can be dynamic or static dependent on the structure used to implement it. If you use an Array is will be a static structure and if you use an ArrayList or Linked List it will be a Dynamic data structure.

The video below shows the Stacks being implemented in an Array (static structure)

Although not in the IB syllabus it is important to see how a stack is implemented into a dynamic data structure.

The video below shows how a stack is implemented into a dynamic data structure.

Below are the same explanations but for the implementation for the Queue

Static Array Implementation of a Queue

Dynamic Implementation of a Queue using a Linked List