Aims

• Know what is meant by the term abstract data type.

• Know what is meant by the term stack and be able to add and remove data from a stack.

• Know what is meant by the term queue and be able to add and remove data from a queue.

• Know what is meant by the term linked list and be able to add and remove data from a linked list.

Abstract Data Types (ADT) refers to: the collection of data organised in some way and the different operations that can be used to manipulate the data.

• Stacks

• Queues

• Linked Lists

Stacks - LIFO (Last in, First Out)

Data held in array and a stack pointer is used to indicate position where data is added/removed. Operations that can be performed on stack:

• Push - Used when adding data to stack

• Pop - Used when you remove data from stack.

Example

Stack with 1D array: theStack with 8 positions, currently holds 3,4,5 in that order.

Pop - Goes to stack and locates position indicated by stack pointer - 3 (Og) and removes the item - 5. Stack pointer is reduced by 1 to look like image 2 (Pop)

Push - Goes to stack pointer - 2 (Pop) and inc by 1, then goes to stack and locates position from stack pointer - 3 and adds data 7 (given in e.g.) to look like image 3 (Push)

How Stacks work

Array sizes have to be declared so only a limited number of elements are available. If all are used and more info is added an error is returned, same as if it was empty and trying to delete info.

When an item is pushed onto the stack:

• Check if stack pointer is = to max

• If it = max it reports the stack is full.

• If not, it inc’s stack pointer by 1

• Then add’s new data to stack indicated by pointer.

When an item is popped from the stack:

• Check if stack pointer = 0

• If it =0 it reports the stack is empty

• If not, it outputs data from stack in position of pointer

• Then reduces stack pointer by 1

Stack Uses e.g.:

• Storeing instructions that can be used in undo mechanisms.

• To reverse word/numbers e.g. ABC to CBA, 123 to 321

• Recursion to store variables within each recursive call.