Design a stack with getmin function

Design one with getMin Stack of functions

【 subject 】

​ Implement a special stack , On the basis of realizing the basic functions of stack , The operation of the smallest element in the return stack .

【 requirement 】

​ 1.pop、push、getMin The time complexity of operation is O（1）.

​ 2. The designed stack type can use the existing stack structure .

【 Ideas 】

​ Use two stacks , A stack a Normal access , Another stack b Used to maintain the minimum value , Always keep b The top of the stack is the current a The minimum value in the stack .

​ Method 1 【 The depth of the two stacks is inconsistent 】： When entering the stack , Each entry a When the stack , If b The stack is empty. , Enter into a The stack enters at the same time b Stack , If you enter a Stack value ratio b The top of the stack is big , No entry , conversely , Get into b Stack , Update minimum ; Out of the stack , If the stack value is equal to b To the top of the stack , Just put b At the top of the stack , Update minimum , conversely ,b Stack does not update .

give an example ： Press in in turn 3、4、5、1、2、1 In the process of ,stackData（a） and stackMin（b） The changes are shown in the figure below .

explain ： The picture comes from Zuoshen's program code interview guide , For learning purposes only .

​ Method 2 【 The two stacks have the same depth 】： When entering the stack , Get into a Stack time , If b The stack is empty. , Get into b Stack , If b Stack is not empty and b Stack top less than a Stack new stack value , Then put the b The top of the stack is pushed again