5.4 KiB
Stacks
- who does not know stack?
Stack
-
what are the two most basic operations in a stack?
- peek can be implemented as pop then push same
-
Stack is a LIFO datastructure.
-
You can only operate on the top
-
where have you used stacks?
- undo
- recursion
- pile of stacks
Quick
- push_bottom a stack using an auxillary stack
- lifo
- reverses when popped
- equivalence with recursion
- anything using a stack can be done using recursion
- draw tree for push_bottom
- how to implement recursion iteratively using stack?
Stack in recursion?
- push state of function call before calling a sub-function
- Call stack
- Example
def fact(n): if n <= 1: return 1 return n * fact(n-1) print(fact(3))
- Call stack
fact(1) fact(2) fact(3) print main
What is stackoverflow?
- How is memory managed?
- 4 types of memory alloted to a program
HEAP Stack (call stack) Global / Static Variables Text / Code
- Each memory is fixed. Compiler / JRE / Interpretter takes care of that.
- So stackoverflow is when you have a very deep recursion
- infinite recursion
Reverse a Stack
2 auxilarry stacks
[1 2 3 4]
[]
[]
[4 3 2 1]
[]
[]
[1 2 3 4]
[4 3 2 1]
[]
[]
O(n)
Via recursion:
def reverse(stack):
x = pop()
reverse(stack)
push_bottom(x, stack)
O(n^2)
time
This uses 2 stacks too, one for recursion, one for push_bottom
Undo-Redo
- Only undo? 1 stack
- Undo-Redo? 2 stacks
- Example of browser history:
- Click pages, push to undo-stack
- go back, pop from undo-stack and push in redo-stack
- go forward, pop from redo-stack and push in undo-stack
Evaluating Post-Fix expressions
- Infix: Inorder
- operator is b/w the operands
a + (b*c) / d
- Postfix: Postorder
- operator is after the operands
bc*d/a+
- Prefix: Preorder
More examples:
- infix:
4 * 5 + (2 - (3 * 4)) / 5
- postfix:
45234*-5/+*
- can I write it as
34*2- \ldots
?- No, because operation need not be commutative (matrix multiplication)
Algorithm for Evaluation:
- go from left to right
- push operands on stack
- when operator, pop top 2 from stack, apply operator, push result
- give example
Convert Infix \to
Postfix
- Convert
(1+2) * 3 / (4 - 5) + 6 - 1
to
21+345-/*61-+
- Precedance:
()
>* /
>+ -
- Can be done in 1 stack
Algorithm:
- 4 decisions to make
- what to do when: operand, operator, (, )
- result = []
- stack = []
- operand:
- append to result
- operator:
- if stack has higher precedance (or equal), apply all of them first
operator: + stack: * * -
- Applying simply means popping from stack and appending to result
- Don't pop (
- if stack has higher precedance (or equal), apply all of them first
- (
- push on stack
- )
- pop from stack until we see (. Pop the ( too
- end
- pop all from stack and append to result
Google Question
N Stock prices for each day
A = [100, 80, 60, 70, 60, 75, 85]
Longest consecutive sequence ending at
i
such that the numbers in the sequence <= A[i] Do this for alli
Exmple output:input: 100, 80, 60, 70, 60, 75, 85 output: 1, 1, 1, 2, 1, 4, 6 include self.
Solution:
- Keep (price, answer) in stack
- traverse array from left to right
- if smaller than stack top price, push (price, 1)
- if larger or equal
- keep popping till larger.
- maintain total answer so far (init by 1)
- once done, push (price, total)
Works because if there was say 59 at the end which would need to stop at 60, it would aready stop at 75
Complexity: O(n)
Each element will be pushed once, and popped at max once
Design a special stack
no restrictions on DS to implement operations
- push
- pop - returns false when stack is empty
- get_mid - returns false when stack is empty
- pop_mid - returns false when stack is empty
all operations must take
O(1)
stack need not be sorted
- can't use array, because how to pop mid in constant?
- use doubly linked list
- keep a pointer to end of list
- keep pointer to mid
- on push, move the mid to right if needed
- on pop, move the mid to left if needed
- for pop mid, pop the mid and update the mid pointer
special MIN stack
use stack internally operations
- push
- pop
- get_min
All operations in
O(1)
Solution 1:
- store both the value, and the min so far into the stack
- can split into two stacks - for values, and for mins if we wish
Further Constraint:
- only 1 stack
- stack can have only 1 value and not tuples
- single space for M (min). init with
\infty
- push:
- if stack empty or E >= M:
- push
- else:
- push T = 2E - M
- M_n = E
this keeps track of previous min
- if stack empty or E >= M:
- get_min
- return M
- pop
- T = top
- if T >= M
- pop and return T
- else
- E = M
- M_o = 2M - T
- return E
Proof:
- If
E < M
, then2E - M < E
. Thus, I can know if the min was changed. - todo: draw diagram by hand