Q1: Explain why Stack is a recursive data structure

https://www.fullstack.cafe/blog/stacks-interview-questions

A stack is a recursive data structure, so it's:

• a stack is either empty or
• it consists of a top and the rest which is a stack by itself;

Q2: Design a Stack that supports retrieving the min element in O(1) time

法一：https://www.fullstack.cafe/blog/stacks-interview-questions

假设用链表：

原本每个节点存的是val，现在每个节点存一个（val， curMin）

push(new_val) 的时候 需要比较 new_val 和 top节点的curMin

space: O(n)

法二：类似法一，我们的special stack里可以存2个普通的stack，stack1存value，stack2存stack1当前的min，stack2.top就是stack1当前的min

https://www.geeksforgeeks.org/design-and-implement-special-stack-data-structure/

法二 can be optimized. We can limit the number of elements in the stack2. We can push only when the incoming element of the stack1 is smaller than or equal to the top of the  stack2. Similarly during pop, if the pop-off element of stack1 equal to the top of the stack2, remove the top element of the stack2.

Followup: Design a stack that supports getMin() in O(1) time and O(1) extra space