Assorted interesting things

Stacks

Last in First out
Only top item is accessible
Undo, recursion, matching brackets
Push(add to top), Pop(get top), peek(see top), (is)empty, (is)full
ADT
Fixed bottom
Pointer value for top
Big O
Pop O(1) Push O(1) Peek O(1)

Queue

Last in last out

Only front item accessible

Enqueue(add back), Dequeue(take front), (see)first,(is)empty,(is)full

Big O

En O(1) De(static head) O(n) De(Dynamic head) O(1)

Assessment

25% CBT (5 short, 20 multi)
75% Exam
Weekly formative quizzes on moodle

Data Structure

Collection of elements
et of associations or relationships

Abstract data type

Input and output data and query object
Do not care what happens inside
Cannot directly access the data inside
Uses getters and setters

ADT vs DS

High level decodeion vs concrete decodeion
Focus on what is can do vs focus on how it manages it
Independent implementation vs dependant implementation

Linear

Unique predecessor and unique successor
Lists, queues stacks

Hierarchical

Unique predecessor and many successors
Trees

Graphs

Many predecessors and many successors
Mesh, web, network

Set structure

No order hence no predecessors and no successors
Group of people

Choosing DS

Analyse the problem
Determine the basic operations
Pick the data structure

Stacks and Queues

Data Structures:

A programatic way of storing data so that it can be used efficently by the program

Abastract Data Type:

A Mathmatical model for a data types (Stack, Queue, Graph) (An Application that uses an ADT is not concerned how the data is stored, and the abstract data type is not concerned how the application uses it.)

Stacks

Like an array, but data that is sent to the array gets added to the end, and you can only acess the last element in the array (first in, last out) Works like a pile of dirty dishes, most recent gets cleaned first.

Queue

Like an array, but data that is sent to the array gets added to the end, and you can only acess the first element in the array (first in, first out) This works like a queue in normal life (eg, at a cafe)