6.3. Stacks and Queues¶
6.3.1. Container Class Design Issues¶
Storing a record vs. Storing a reference to a record
Homogeneity: Allow different record types? Check and block?
Deletion: What happens to the record?
6.3.2. Stacks¶
LIFO: Last In, First Out.
Restricted form of list: Insert and remove only at front of list.
Notation:
Insert: PUSH
Remove: POP
The accessible element is called TOP.
6.3.3. Stack ADT¶
6.3.4. Array-Based Stack (1)¶
Issues:
Which end is the top?
Where does “top” point to?
What are the costs of the operations?
6.3.5. Array-Based Stack (2)¶
6.3.6. Linked Stack¶
What are the costs of the operations?
How do space requirements compare to the array-based stack implementation?
6.3.7. Queues¶
FIFO: First in, First Out
Restricted form of list: Insert at one end, remove from the other.
Notation:
Insert: Enqueue
Delete: Dequeue
First element: Front
Last element: Rear
