SLR14 - Data Structures

Array

• Variable that can contain more than one data item eg. list of names

• Allocate contiguous(stored together, simultaneously) parts of memory

One dimensional arrays

• Eg: countries = [“Angola”, “Austria”, “Belgium”]

• Sets up one dimensional array called countries

• Index starts 0

• static structure - cant change size array once set up

• Can insert item into new location at end of array using index

Two dimensional array

• Can visualise as table with two sets of index

• Eg: Countries[0][0] is an item location

Record data structure

• Collection of related fields

• Field - variable and each field in record can have different data type

steps to use record data structure

1. Define record structure - what field will be in record

2. Declare variable or array to use within record structure

3. Assign & retrieve data from variable record

Lists

• Mutable

• Item can be changed & replaced

• Can store more than one data type

Array

• Mutable

• item can be changed or replaced

• Store only one data type

Tuple

• Immutable

• item cannot be changed or replaced

• Can store more than one data type

Stacks

• Data structure where items pushed on top of stack when added to it and popped off top when deleted

• Last in first out - LIFO

Stack pointer

Points to top item

How are stacks implimented

Often using an array but can also be created using object orientated techniques

What are applications of stacks

• Used by processor to track flow of program

• When sub-routine called

• Used for:

  • Keep track of user inputs for undo operations

  • Backtracking algorithms

Operations that can be performed on a stack

• Push: add item to top

• Pop: Remove item from top

• Peek: Returning value from the top of stack without remove it

Queues

• Linear data structure

• Items are enqueued at back of queue & dequeued from front

• First in first out -FIFO

How queues implemented

Queues can be implemented using array or object oriented technique

Circular queue

• Implemented when using queues with arrays to prevent running out of space

• Cycles back to pointer to front of array when reached end

Applications of queue

• process scheduling

• Transferring data between processors & printer spooling

• Performing breath-first searches on graph of data structure

Operations that can be performed on queue

• Enqueue: adding item to back of queue

• Dequeue: removing item from front of queue

• Peek: returning value from front of queue without removing it