notes10a.pdf

th June 6 Lecture Notes Stacks - 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 ADT Stack 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] Stack Implementations 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. Queues - 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 first g