PHP 定义栈结构，实现min函数，获取栈最小元素，要求时间复杂度为O(1)

 1 <?php
 2     #设计一个栈的数据结构，要求增加一个min函数，可以取出栈的最小元素
 3     #要求push,pop,min的时间复杂度都是O(1)
 4     #解题思路：在每个栈元素增加一个min变量，这个变量存储次元素及其之前所有元素的最小值
 5 
 6     #栈节点
 7     class Node {
 8         public $data = null;
 9         public $min = null;
10     }
11 
12     class Min_Stack {
13         private $data = array();
14         private $top;
15 
16         public function __construct(Array $a) {
17             $this->top = 0;
18             foreach($a as $val) {
19                 $this->push($val);
20             }
21         }
22 
23         public function push($i) {
24             $node = new Node();
25             $node->data = $i;
26 
27             #此处设置每个节点的min值，设置方法为若栈为空，当前元素data则为当前节点的min
28             #若栈非空，则当前元素data与前一个节点的min值比较，取其小者作为当前节点的min
29             if ($this->top == 0) {
30                 $min = $node->data;
31             } else {
32                 $min = $this->data[$this->top - 1]->min < $node->data ? $this->data[$this->top - 1]->min : $node->data;
33             }
34 
35             $node->min = $min;
36             $this->data[] = $node;
37             $this->top++;
38             return $node;
39         }
40 
41         public function pop() {
42             $r = $this->data[--$this->top];
43             unset($this->data[$this->top]);
44             return $r;
45         }
46 
47         public function get_min() {
48             return $this->data[$this->top - 1]->min;
49         }
50     }
51 
52     $a = array(5, 7, 3, 8, 9, 1, 2);
53     $min_stack = new Min_Stack($a);
54     echo "Min : {$min_stack->get_min()} <br>";
55     print_r($min_stack);
56     echo "<br> Pop : {$min_stack->pop()->data}<br>";
57     print_r($min_stack); 
58 ?>

Min : 1
Min_Stack Object ( [data:Min_Stack:private] => Array ( [0] => Node Object ( [data] => 5 [min] => 5 ) [1] => Node Object ( [data] => 7 [min] => 5 ) [2] => Node Object ( [data] => 3 [min] => 3 ) [3] => Node Object ( [data] => 8 [min] => 3 ) [4] => Node Object ( [data] => 9 [min] => 3 ) [5] => Node Object ( [data] => 1 [min] => 1 ) [6] => Node Object ( [data] => 2 [min] => 1 ) ) [top:Min_Stack:private] => 7 )
Pop : 2
Pop : 1
Min : 3
Min_Stack Object ( [data:Min_Stack:private] => Array ( [0] => Node Object ( [data] => 5 [min] => 5 ) [1] => Node Object ( [data] => 7 [min] => 5 ) [2] => Node Object ( [data] => 3 [min] => 3 ) [3] => Node Object ( [data] => 8 [min] => 3 ) [4] => Node Object ( [data] => 9 [min] => 3 ) ) [top:Min_Stack:private] => 5 )