Please don\'t take handwriting picture. Please type the answer. Please don\'t ta
ID: 3755128 • Letter: P
Question
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.Please don't take handwriting picture. Please type the answer.Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
Please don't take handwriting picture. Please type the answer.
ALGORITHM Propose a data structure that supports the stack operations PUSH, POP, and a third operation FIND MIN which returns the smallest element in the stack (does not delete the element). All three operations should run in O(1) worst case time. Write algorithms for the three operations Provide an example (with actual numbers) to show how each algorithm works.Explanation / Answer
minElement keep track to minimum element stack is holding.
(1)PUSH(x) : Insert x at the top of stack.
If stack is empty, insert x into the stack and make minElement equal to x.
If stack is not empty, compare x with minElement.
Two cases arise:
(a)If (x>= minElement) simply insert x.
(b)If (x< minElement) insert (2*x - minElement) into the stack and minElement= x.
(2)POP : Removes an element from top of stack.
Let the removed element be y.
Two cases arise:
(a)If (y>= minElement) then minimum element in the stack is still minElement.
(b)If (y< minElement) minElement = 2*minElement - y.
(3)FINDMIN() : return minElement;