最小栈的实现

题目
实现一个栈，该栈带有出栈（pop）、入栈（push）、取最小元素（getMin）3个方法。要保证这3个方法的时间复杂度都是O(1)。

image.png
详细的解法步骤如下：

1. 设原有的栈叫作栈A，此时创建一个额外的“备胎”栈B，用于辅助栈A。

   
   image.png

2. 当第1个元素进入栈A时，让新元素也进入栈B。这个唯一的元素是栈A的当前最小值。

   
   image.png

3. 之后，每当新元素进入栈A时，比较新元素和栈A当前最小值的大小，如果小于栈A当前最小值，则让新元素进入栈B，此时栈B的栈顶元素就是栈A当前最小值。

   
   image.png

4. 每当栈A有元素出栈时，如果出栈元素是栈A当前最小值，则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的，是栈A当中原本第2小的元素，代替刚才的出栈元素成为栈A的当前最小值。（备胎转正。）

   
   image.png
5. 当调用getMin方法时，返回栈B的栈顶所存储的值，这也是栈A的最小值。

具体代码如下：

class Code{

    public $stack = array();
    public $minStack = array();

    function stackPush($data){
        array_push($this->stack, $data);
        if(!$this->minStack || end($this->minStack) > $data){
            array_push($this->minStack, $data);
        }
    }

    function stackPop(){
        $stackTop = array_pop($this->stack);
        if($stackTop == end($this->minStack)){
            array_pop($this->minStack);
        }
        return $stackTop;
    }

    function getMin(){
        if(!$this->minStack){
            var_dump("栈为空");
        }
        return end($this->minStack);
    }
    
}
$obj = new Code();
$obj->stackPush(9);
$obj->stackPush(4);
$obj->stackPush(7);
$obj->stackPush(3);
var_dump($obj->stack);
var_dump($obj->getMin());
$obj->stackPop();
var_dump($obj->stack);
var_dump($obj->getMin());

输出结果：

image.png