June 6 Lecture Notes
- Also called push down stacks
- A stack is a linear collection of items, addition and removal of items in a stack take place from exactly
one (the same) end called the LIFO Protocol (Last In First Out)
- Example: a garage with one door that can hold 3 cars: Car three comes in last and has to go out first,
car 1 comes in first but can only go out last
|Car1 Car2 Car3| garage door with 3 cars in the garage
- Another example is a tennis ball container – the last in tennis ball is the first out tennis ball
- Push: add to the top; pop = remove from the top
Data: Linear collection of items
Operations: Stack() – creates an empty stack
isEmpty() – is the stack empty?
length() – number of items in the stack
push(item) – add item to the top of the stack
pop() – remove an item from the top of the stack
peek() – returns the top item without removing it
Using the Stack ADT
L = [5,10,2,-1,8,9,11]
What is the value of L after this code has executed?
The code takes element 1 of L and pushes in onto the stack, continues to do this
until the list becomes empty.
Then until stack is empty, pop off the top value of stack repeatedly and append it to L.
At the end of the two while loops, L = [11,9,8,-1,2,10,5]
Several common ways to implement a stack in Python:
- Python list: Easy to implement but there are still multiple ways of doing it depending on where we want
the top to be
- Linked Lists: Better choice when there are a large number of items and a large number of push and pop
operations are performed.
Application of Stacks
Balanced parenthesis problem ()()(), ((()))() etc. are balanced parenthesis
- Push each opening parenthesis onto the stack
- Upon observing a closed parenthesis, pop from the stack
- if the stack is empty at the end, the string is balanced
Evaluating Mathematical Expressions
Example: 4 + 3 * 5 = 4 + (3*5) = 19
Postfix = 4 3 5 * +. How does the computer evaluate this? - Evaluation Stack: if we have a value push it into the stack, when we get an operand take the top two
values in the stack, pop them off and perform the operand on them. Push the result back onto the stack
and repeat until we are done.
- Example: es = |5,3,4| pop off 5 and 3, get 15, now the stack is |15,4|. The next operand is + so pop off
two items in the stck (4 and 15) perform the operation (4 + 15), get 19 and push it onto the stack. Since
there are no more operands and only one value, 19 is the final answer.
- Another linear collection of items
- Addition to the collection and removal from the collection happen at opposite ends
- FIFO protocol (first in first out)
- Examples: people in a queue (first in line gets served first)
- Example: a network of computers printing from a common computer. The document sent to the printer