Stewart Coetzee
Data structures
in Python
Week 1
Stacks, Queues, Deques & Recursion
Firstly… Who is this guy?
• Mr Stewart Coetzee
• Studied at The University of Pretoria
• Love teaching and programming
• I also play the ukelele :)
I was not here last week
What happened?
What did you learn?
What do you know?
What don’t you know?
Are we good to go?
Learning Outcomes
Understand and implement recursion
- Stacks
Understand and implement - Queues
- Deques
Recursion
Just a more complicated loop
Loops first
While loop, for loop
Allows a set of code to run multiple times
Either for a fixed or unknown number of times
Can call functions in your loop
Normal loop example
Recursive Functions
A function that calls itself
The function will run again while it’s already running
Will run endlessly unless a return is encountered
Example:
Recursion
There MUST be a base case
Begin by testing for a / a set of base case(s)
Every possible chain of recursive calls MUST eventually reach a base case
Perform a single recursive call
Make progress towards a base case
Recursion example
n=6
Let’s put it to the test
1AB23CD45EF6
n=6
The Factorial pattern – a classic
The factorial adds all numbers from 1 to n
Such as: 7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040
Easy to use a loop, right?
The Factorial pattern – a classic
Now, lets look at it from another angle
4! = 4 x 3 x 2 x 1
4! = 4 x 3!
3! = 3 x 2!
And so on and so forth and what have you
Let’s make this function!
Draw a recursion trace
Let’s put it to the test… but harder
hello
mark
h*ll*
kram
The English ruler
Looks confusing
Because it is
But let's break it down
The English ruler
The English ruler
Breathe
Write a recursive function
This recursive function should
Reverse an inputted string
Have 1 recursive call
Have 1 base case
Binary Search
Used to find a specific value in a sorted array/list
We could use a loop.. Why not?
PS binary means 2 :)
File systems
Tail Recursion
When a recursive function makes its recursive call as its last step
Binary recursion
When there are two recursive calls for each non-base case
Multiple recursion
A function may make more than two recursive calls
Breathe
…again
Stacks
Exactly what it sounds like
What are we stacking now?
Let’s recall abstract data types (ADTs)
An abstraction (outline) of a data structure
Specifies the data types and operations
As well as error conditions
The Stack data structure
Stores a sequence/number of variables
Last-In-First-Out LIFO
Push() means add
Pop() means remove
But let’s go a bit deeper
The Stack data structure
1. push(3)
2. push(5)
3. pop()
1 4. push(7)
7
5 5. push(1)
3 6. pop()
The Stack data structure
top() returns the last entered element [without removing it]
len() returns the number of elements
is_empty returns true if there are no elements
push(i) adds an element
pop() removes AND returns the last added element
The Stack data structure
Array-based stack
Uses an array to store the stack elements
Elements are stored from left to right
Elements are added and removed on the right side
Array-based stack
Why would we a
Stack?
Applications of Stacks
Undo/redo operations
Browser history
Web navigation
Balancing <html> tags or parenthesis
Still breathing?
Let’s code!
Implement your own stack using an array
Make sure to include the following:
pop and push
size()
second() – the second element that will be removed
last() the element at the bottom of the stack
int remove_all() removes all elements and returns the number of elements removed
print_stack() prints the elements from top to bottom: 1 | 2 | 3 | 4
Queues
Also, exactly what it sounds like
The Queue data structure
Stores a sequence/number of variables
First-In-First-Out FIFO
enqueue() means add
dequeue() means remove
But let’s go a bit deeper… again
The Queue data structure
Elements are added to the back
And elements are removed from the front
(like a queue in the real world… crazy)
first() – next element to be removed – without removing it
len() – number of elements
is_empty() – true if there are no elements
enqueue() and dequeue()
The Queue data structure
1. push(7)
2. push(1)
3. pop()
4. pop()
9 1 7 1 6 2
5. push(9)
6. pop()
The Queue data structure
Array-based Queue
Uses a circular array to store the queue elements
Elements are stored from left to right
Elements are added to the right
Elements are removed from the left and shifted
Why would we a Queue?
Applications of Queues
Round-robin schedulers
Print queue
Customer service tickets
Web server request
Deque
Okay, this one isn’t exactly what it
sounds like
Deque: Double-Ended Que(ue)
Works the same as a Queue
But elements can be added and removed from both sides
Basically, works like a Stack and Queue
… but don’t quote me on that
Deque: Double-Ended Que(ue)
add first(el): Add element el to the front of Deque.
add last(el): Add element el to the back of Deque.
delete first () : Remove and return the first element
delete last (): Remove and return the last element from deque
Deque: Double-Ended Que(ue)
first (): Return (but do not remove) the first element
last (): Return (but do not remove) the last element is
is_empty(): Return true if deque D does not contain any elements.
len(D): Return the number of elements in deque D
Deque: Double-Ended Que(ue)
Write some code
Write a recursive function to remove all elements from a queue
Write a recursive function to remove all elements from a stack
Each should return the number of elements removed
(Assume stack s and queue q are already implemented data structures)
Write some code
Deque implementation
That’s all
Folks
I’ll be here all week
not really
