(3.25 a) Propose a data structure that supports the stack push and pop operation
ID: 3712588 • Letter: #
Question
(3.25 a) Propose a data structure that supports the stack push and pop operations and a third operation findMin, which returns the smallest element in the data structure, all in O(1) worst-case time. When you are convinced you have a working design, write a Java class that implements your proposed data structure (with methods). Include a block comment at the top of the Java file that describes your proposed data structure, so that the design documentation and the code are contained in a single file.
Explanation / Answer
We can use two stacks S1 and S2 I.e push the elements to S1 , present minimum is solely pushed to S2 .
If required to insert an element E ,initially push E to S1 furtherly acess the top element P from S2 that was minimum previously E was inserted .it is done only when T is greater than E then push E to S2.
if required to pop the element in S1 ,pop the peak element in S2. so suppose such element is often similar to the peak of S2 , furtherly pop it off also.
Therefore the present minimum element would all the time on top of S2. so including further stack manipulations ,acess of minimum elemnet is often feasible with O(1) worst _case time.
Is the Design Right ? WHAT DO YOU THINK ? Comment and then we can write Java Code for it
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.