Definition
Queue: Abstract data type with the following operations
- Enqueue(Key): adds key to collection
- Key Dequeue(): removes and returns least recently-added key
- Boolean Empty(): are there any elements?
FIFO: First-In, First-Out
Queue Implementation with Linked List
- Enqueue: use List.PushBack
- Dequeue: use List.TopFront and List.PopFront
- Empty: use List.Empty
Queue Implementation with Array
Keep track of array as a circular array
- Enqueue: write
- Dequeue: read
- Empty: read is equal to write
Summary
- Queues can be implemented with either a linked list(with tail pointer) or an array.
- Each queue operation is O(1): Enqueue Dequeue Empty
Distinction
Array: a maximum size that queue can grow to(bounded).
Any amount that is unused is wasted space
Queue: get arbitrarily large as long as there’s available memory
Downside is every element u have to pay for another pointer