Stacks and Queues
Robert Horvick
SOFTWARE ENGINEER
@bubbafat www.roberthorvick.com
Stacks
- Last-in, First-out data structure
Overview Queues
- First-in, First-out data structure
Deque
- Double-ended queue
Demo: Contact Manager
- Undo
- Flight Recorder
Stack
A Last-in, First-out (LIFO) data container.
The stack of plates is
initially empty
EMPTY
Additional plates can
be added to the stack
We can only access
the plate at the top of
the stack
The stack of plates is
now 4 deep
There is a top plate
and a bottom plate
top
bottom
Plates come off the
top of the stack
top
bottom
We “pop” items off
the stack
top
bottom
A single item is the
top and bottom
bottom top
Popping the last
item empties the
stack
EMPTY
Queue
A First-in, First-out (FIFO) container.
”Queuing” in a line
Enqueue at end of
line
First is “head”
Last is “tail”
tail head
The head of the line is
“dequeued”
Next is now “head”
tail head
A new person waits
at the end of the line
tail head
The queue gets
shorter
The queue gets
shorter
The queue gets
shorter
The queue gets
shorter
Until it is empty
Doubly Ended Queue (deque)
A queue-like container which is both First-in, First-out
and Last-in, Last-out.
Doubly Ended Queue
Start with an empty queue
Tail Head
Doubly Ended Queue
Start with an empty queue
3
Add ”3” to the head Tail Head
Doubly Ended Queue
Start with an empty queue 2 3
Add ”3” to the head
Tail Head
Add “2” to the tail
Doubly Ended Queue
Start with an empty queue
Add ”3” to the head
2 3 4
Add “2” to the tail Tail Head
Add ”4” to the head
Doubly Ended Queue
Start with an empty queue
Add ”3” to the head 1 2 3 4
Add “2” to the tail
Tail Head
Add ”4” to the head
Add “1” to the tail
Doubly Ended Queue
Start with an empty queue
Add ”3” to the head
Add “2” to the tail
1 2 3 4 5
Add ”4” to the head Tail Head
Add “1” to the tail
Add “5” to the head
Doubly Ended Queue
1 2 3 4
Remove “5” from the head
Tail Head
Doubly Ended Queue
Remove “5” from the head
2 3 4
Remove “1” from the tail Tail Head
Doubly Ended Queue
Remove “5” from the head 3 4
Remove “1” from the tail
Tail Head
Remove “2” from the tail
Doubly Ended Queue
Remove “5” from the head
Remove “1” from the tail
3
Remove “2” from the tail Tail Head
Remove “4” from the head
Doubly Ended Queue
Remove “5” from the head
Remove “1” from the tail
Remove “2” from the tail
Remove “4” from the head Tail Head
Remove the “3” from the
tail or head
Demo
Use a Stack to add an “Undo” operation
Use a Queue to add a flight recorder log
