Home » Data Structure & Algorithms » Special Stack Data Structure which returns minimum and maximum element in O(1) complexity.

Special Stack Data Structure which returns minimum and maximum element in O(1) complexity.

Question :

WAP to design special stack data structure which returns minimum and maximum element in  O(1)  complexity.

Algorithm :

Declare 3 Stacks specialStack,minStack and maxStack.

Push(Object data) 
         Step 1 : push data to the specialStack(actual stack)
         Step 2 : compare data with the top element of the minStack . Let the top element of minStack be element.If data is smaller than element then push data to the minStack .If data is greater than element then push data to the minStack .compare data with the top element of the maxStack . Let the top element of maxStack be element.If data is greater than element then push data to the maxStack .If data is smaller than element  then push data to the maxStack .

int Pop() 
            Step 1 :  pop the top element from the minStack and maxStack.
            Step 2 : pop the top element from the specialStack  and return it.

int getMin() // returns the minimum element from Special Stack
                 Step 1 : Return the top element of minStack.

int getMax() // returns the maximum element from Special Stack
                 Step 1 : Return the top element of maxStack.

All above operations are O(1) time complexity.

Program :

OutPut :

 
 


Leave a comment

Your email address will not be published. Required fields are marked *

14 − ten =