札记之PHP实现包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1）)

思路

• 定义2个栈，一个正常存数据，一个作为辅助栈来存最小值；
• 因为辅助栈的栈顶元素最当前栈中的最小值，每次push比较入栈元素和辅助栈栈顶元素，小的则放入辅助栈；

图示

代码实现

class minStack
{
    private $stack;
    private $minStack;
    private $top = -1;

    public function __construct()
    {
        $this->stack = [];
        $this->minStack = [];
    }

    public function push($data = null)
    {
        //初始化，栈顶为空时
        if ($this->top == -1) {
            array_push($this->stack, $data);
            array_push($this->minStack, $data);
            $this->top++;
            return true;
        }

        //如果不为空，判断入栈的值是否比最小栈栈顶小
        $min = $this->minStack[$this->top];
        //比较出最小值
        $newMin = $data < $min ? $data : $min;
        //栈中的最小值入栈
        array_push($this->minStack, $newMin);
        array_push($this->stack, $data);
        
        $this->top++;
        return true;
    }

    public function pop()
    {
        if ($this->top === -1) {
          return false;
        }
        
        array_pop($this->minStack);
        $this->top--;
        return array_pop($this->stack);
    }

    public function min()
    {
        return $this->minStack[$this->top];
    }
}

$stack = new minStack();
$stack->push(5);
$stack->push(6);
$stack->push(3);
$stack->push(8);
$stack->push(9);

print_r($stack->min());

$stack->pop();
$stack->pop();
$stack->pop();
print_r($stack->min());

结果：

35