包含min函数的栈

题目描述

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

注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

分析

除了一个正常入栈出栈的栈结构 A，还需要一个维护栈 A 最小值的栈 B。

1. 一开始，节点入栈 A后，因为栈 B为空，所以就直接入栈。
2. 再有节点入栈 A时，要判断节点是否比栈 B的栈顶小，如果是，则也入栈 B。
3. 栈 A节点出栈后，要判断节点是否等于栈 B栈顶，如果是，则栈 B栈顶也出栈。

代码

<?php
namespace app\Test\controller;

class Test
{
    public static $stack    = NULL;    // 栈
    public static $minStack = NULL;    // 存放最小值的栈

    // 入栈
    public function push($node)
    {
        if (empty(self::$stack)) self::$stack = new \SplStack();        // 实例化
        if (empty(self::$minStack)) self::$minStack = new \SplStack();  // 实例化

        self::$stack->push($node);  // 入栈

        // 如果 $minStack 为空，或者当前 node 的值小于 $minStack 的栈顶，则压入 $minStack
        if (self::$minStack->isEmpty() || $node < self::$minStack->top())
            self::$minStack->push($node);

        return self::$stack;
    }

    // 出栈
    public function pop()
    {
        $node = self::$stack->pop();     // 出栈
        $top  = self::$minStack->top();  // $minStack 的栈顶

        // 如果出栈的 node 等于 $minStack 的栈顶，则 $minStack 的栈顶也要出栈
        if ($node == $top) self::$minStack->pop();

        return $node;
    }

    // 栈顶
    public function top()
    {
        return self::$stack->top();
    }

    // 栈的最小值
    public function min()
    {
        return self::$minStack->top();
    }

    // 测试
    public function test()
    {
        // 入栈：5、6、1、9、10、3
        $this->push('5');
        $this->push('6');
        $this->push('1');
        $this->push('9');
        $this->push('10');
        $this->push('3');
        // 出栈：3、10
        $this->pop();
        $this->pop();

        print_r(self::$minStack);             // 栈：5、1
        echo "</br>";
        print_r(self::$minStack->count());    // 栈底：2
        echo "</br>";
        print_r(self::$minStack->bottom());   // 栈底：5
        echo "</br>";
        print_r($this->min());                // 栈的最小值：1
        echo "</br>";
        print_r($this->top());                // 栈顶：9
    }
}

笔记

SplStack 类：通过使用一个双向链表来提供栈的主要功能。