Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM10 - Coggle Diagram
MM10
Queues
List-like
Implementations
of ADT
Array Based
Tricky to implement
current rear
current front
Not efficient unless
properly implemented
Enqueue - O(1)
Dequeue - O(n)
Allowing the contents to
move along helps efficiency
But might miss free space
Can be fixed by turning
the array into a circle
Linked Queues
Straightfoward
LL adaptation
Header link node for Enqueue
Avoids cases where it`s empty
Rear points to last link node
On startup points to header
Comparison of
Array/Linked Queues
Both require O(1)
Size advantage is the same as Stacks
No easy way to store
two queues in an array
Restricted acess
Enqueue - Insert to back
Dequeue - Remove from front
Similar to a line
FiFo List
Stacks
LIFO Policy
Restrictive
More efficient
Easy to implement
Implementations
of ADT
Array Based
Fixed size
Top - Current position
Top pos - Tail
"Simplified" array list
Linked Stacks
Freelist
Removed and inserted from end
No header node required
List-like
"Lifo List"
Comparison of
Array/Linked Stacks
No significant
time advantage
Size advantage
Array - Might waste space - Fixed size
Linked - Shrinks and Grows - Requires overhead
2 Linked Stacks
1 Array Stack
Can be inserted into the Array
Ideal implementation could lead to less wasted space
If one grows, the other shrinks