AQA COMPUTER SCIENCE A LEVEL - FUNDAMENTALS OF DATA STRUCTURES

What is a stack?

abstract data type where the last item added to the stack is the first to leave (LIFO)

Where are stacks used?

in calculations,

holding return addresses when subroutines are called,

back button on web browser,

undo button on word processr

How are they implemented

dynamic (list)

static (array with two pointers)

test if stack is empty

stack.isEmpty()

return True/False

test if stack is full

stack.isFull()

return True/False

return top item from stack but not remove

stack.peek()

return top item

remove and return top item

stack.pop()

return top item

add new item to top of stack

stack.push(item)

what is stack overflow?

when an item is attempted to be pushed onto a stack but the stack is full

what is stack underflow?

when the stack is empty and an item is being attempted to be popped

pseudocode to push onto stack

SUB pushToStack

IF topOfStack = maxSize THEN

OUTPUT "Stack is full - no space available"

ELSE

INPUT newStackItem

topOfStack = topOfStack + 1

stack(topOfStack) = newStackItem

ENDIF

ENDSUB

pseudocode to pop from stack

SUB popFromStack

IF (topOfStack = 0) THEN

OUTPUT "Stack is empty - no data to pop"

ELSE

OUTPUT stack[topOfStack]

topOfStack = topOfStack - 1

ENDIF

ENDSUB

What is a stack frame?

stores information about active subroutines while computer programs are running

holds return addresses

What is a data structure?

a collection of elementary data types

What is an elementary data type?

contains single data values

e.g.boolean, integer, real, char

What is a composite data type?

constructed using elementary data types

e.g. string, array, list

What is a structured data type?

sequence of characters

What is an abstract data type?

logical description of how we view the data and possible operations

What are some examples of abstract data types?

queue

stack

graph

tree

hash table

dictionary

vector

What is data abstraction?

hiding details on implementation

What is a dynamic data structure?

a collection of data in the memory that has the ability to grow or shrink in size with the aid of a heap

What is a heap?

a portion of the memory from which free space is automatically allocated or de-allocated as required

What is a static data structure?

fixed in size and cannot increase in size or free up memory whilst the program in running

What is a queue?

abstract data structure that operates on a first in, first out (FIFO) basis

where data is pushed into the queue and popped from it

Examples of queues in real life

printer - print jobs sent, print one at a time in order sent

keyboard - characters entered appear in order sent

Where is the front of a queue?

0

Where is the rear of a queue?

-1

how to ADD item to the REAR of the queue

enQueue(item)

how to REMOVE item from queue FRONT

deQueue

returns item from queue front

how to check if queue is EMPTY

isEmpty

returns True/False

how to check if queue is FULL

isFull

returns True/False

how to check queue SIZE

size

returns how many items in queue

how to check queue MAX SIZE

MaxSize

returns the max number of items that can be stored

What are the types of queue?

Linear

Circular

Priority

What is a linear queue?

organised as a list or line of data

How to implement a linear queue? (1)

(1) when an items leaves, items move up

so FRONT has an element

if the queue is long, there is a long processing time as each item is moved

How to implement a linear queue? (2)

(2) using FRONT/REAR pointers

move pointers as necessary

as items are deleted, there is unused space accumulating at the front

What do the start(front) and end(rear) pointers show?

start show the data item that was entered first into the queue

end show the data item that was entered last into the queue

What is a circular queue?

organised in a ring where the start and end pointers wrap around from the last to the first element in the array

Circular queue pseudocode - initialise

SUB initialise

front = 0

rear = -1

size = 0

maxSize = size of array

ENDSUB

Circular queue pseudocode - test for empty queue

SUB isEmpty

IF size == 0 THEN

RETURN True

ELSE

RETURN False

ENDIF

ENDSUB

Circular queue pseudocode - test for full queue

SUB isFull

IF size == maxSize THEN

RETURN True

ELSE

RETURN False

ENDIF

ENDSUB

Circular queue pseudocode - add element to the queue

SUB enqueuer(newItem)

IF isFull THEN

OUTPUT "Queue Full"

ELSE

rear = (rear + 1) MOD maxSize

q(rear) = newItem

size = size + 1

ENDIF

ENDSUB

What is a priority queue?

similar to regular queue but

each element assigned a priority

highest priority items are first

(where priority is same, then FIFO)

What is a hash table?

stores data in an associative way

the table is created by using a hash function which maps a key to an index in an array to find the value of an array element

What are the uses of hash tables?

efficient lookup (implementing with dictionary)

e.g. finding data, passwords

What is a hash function?

a calculation applied to the value in the key field of each record to transform it into an address

Mid Square Method

1) square the item

2) extract a portion of resulting digits

3) resulting digits MOD tableSize

Folding Method

1) Divide the item into equal size pieces (last may not be)

2) Add pieces together

3) resulting number MOD tableSize

How would you hash alphanumeric data?

Use the ASCII code equivalents for each char then apply the function

What is a collision?

when two keys are applied to the hash function and create an identical hash value

A good hashing algorithm...

...aims to minimise the chance of collisions

How can the table help with collisions?

designed so 50-70% of tables cells are occupied (as the fuller the hash table, the more likely a collision)

prime number of cells, so when MOD tableSize performed more likely to get different values

What are the two methods to deal with collisions?

Linear probing and separate chaining

What is linear probing?

where a key is assigned to the next available slot in the hash table (if there is a collision)

What is the problem with linear probing?

can create clustering (where more collisions can occur as the hashing function index is not randomly distributed)

How to improve linear probing?

increment search for next empty cell in 1,3,5,7,etc to reduce cluster

What is a linked list?

a linear data structure in which a group of nodes contain data and make use of a pointer to link with the next data element

What is separate chaining?

where the hash table index is a pointer to a linked list data structure that contains all the data

where there are no collisions the linked listed contains one element and the linked list will contain all the collisions for a particular slot

What are collisions also known as?

synonyms

How are items found in hash table?

algorithm applied to item and examine resulting cell (index)

if item is there, return item

if cell is empty, then not in table

if there is a different item in that spot or message saying that the item is this cell has been deleted, keep moving until met with item or empty spot

What is a linear search?

start at the beginning, go through everything in order

sequential search

What is a binary search?

(provided data is ordered)

split data in half

would it be before/after?

repeat

quicker than linear search

What is a dictionary?

contains a collection of 'key-value' data elements where the data value is accessed by the associated key

associative array

multiple items associated with the same key are...

...not allowed

multiple values associated with the same key are...

...allowed

How are key-values pairs stored in a dictionary?

in no particular order

what opereations can you do on a dictionary

create a new empty dictionary

add new key:value

delete key:value

ammend key:value

return value associated with key

return True/False if key in dictionary

return length of dictionary