adt - Design stack so that getminimum, pop, push & top all takes O(1) -

adt - Design stack so that getminimum, pop, push & top all takes O(1) -

so asked question:

consider adt stack. in add-on operations push, pop , top, want back upwards new operation findmin, returns smallest element in stack. design info construction , algorithms back upwards these operations such each of 4 operations (push, pop, top , findmin) takes constant time. no need check on , under conditions , no need give procedures empty , full. [hint: utilize stack.]

so have seen answers seemed take o(n) time 1 time findmin function used. , don't hint trying tell me...please help me!!! thankssss!!

import java.util.stack; public class stackwithmin extends stack<integer> { private stack<integer> minstack; public stackwithmin () { minstack = new stack<integer>(); } public void push(int value){ if (value <= min()) { // note '=' sign here minstack.push(value); } super.push(value); } public integer pop() { int value = super.pop(); if (value == min()) { minstack.pop(); } homecoming value; } public int min() { if (minstack.isempty()) { homecoming integer.max_value; } else { homecoming minstack.peek(); } } public static void main(string args[]) { stackwithmin stackwithmin = new stackwithmin(); stackwithmin.push(7); stackwithmin.push(5); stackwithmin.push(6); stackwithmin.push(7); stackwithmin.push(4); system.out.println(stackwithmin.min()); stackwithmin.pop(); system.out.println(stackwithmin.min()); }

}

stack adt