<?php
/**
 * 使用一個(gè)輔助棧，O(1)復(fù)雜度求出棧中的最小數(shù)
 * @hack 類中通過(guò)數(shù)組來(lái)模擬堆棧
 * 
 * @author laiwenhui
 */
class strack{

  /**
   * 數(shù)據(jù)棧，存儲(chǔ)棧數(shù)據(jù)；
   *
   * @var array
   */
  private $_arrData = array();
  /**
   * 輔助棧，存儲(chǔ)數(shù)據(jù)組棧中每層的最下值信息；
   *
   * @var array
   */
  private $_arrMin = array();
  /**
   * 棧頂所在單元
   *
   * @var int
   */
  private $_top=-1;
  /**
   * 出棧
   * @return bool|int
   */
  public function pop(){
    if ($this->_top === -1){
      return false;
    }
    array_pop($this->_arrMin);
    $this->_top--;
    return array_pop($this->_arrData);
  }
  /**
   * 入棧
   * @param int $element
   * @return bool
   */
  public function push($element){
    $element = intval($element);
    //如果棧為空，直接入棧
    if ($this->_top === -1){
      array_push($this->_arrData, $element);
      array_push($this->_arrMin, $element);
      $this->_top++;
      return true;
    }
    //不為空，判斷入棧的值是否比最小棧棧頂小
    $min = $this->_arrMin[$this->_top];
    //比較求出最小值
    $currentMin = $element < $min ? $element : $min;
    //當(dāng)前棧中最小值入棧
    array_push($this->_arrMin, $currentMin);
    //數(shù)據(jù)入棧
    array_push($this->_arrData, $element);
    $this->_top++;

    return true;
  }
  /**
   * 求當(dāng)前棧空間的最小值
   * @return bool|int 
   */
  public function min(){
    if ($this->_top === -1){
      return false;
    }
    return $this->_arrMin[$this->_top];
  }
}