数据结构随笔-php实现栈

栈(Stack)满足后进先出(LIFO)的原则;

下面利用php实现栈的相关操作;

本实例栈的基本操作:

入栈(push):向栈内压入一个元素,栈顶指针指向栈顶元素

出栈(pop): 从栈顶去除元素,栈顶指针向栈底移动;

判空(isEmpty):当栈顶指针恢复为初始指针状态即为空栈;

判满(isFull): 当栈顶等于容量减一则栈满;

使用php数组实现一个简单操作的栈;

?php

/**
 * Created by PhpStorm.
 * User: gordon
 * Date: 2017/8/6
 * Time: 12:58
 */

/**
 * Class Stack 简单栈
 */
class Stack
{
    /**
     * 栈初始指针
     */
    const TOP_INIT = -1;

    /**
     * 栈底指针
     */
    const BOTTOM = 0;
    /**
     * @var array 栈数组
     */
    private $_stack;

    /**
     * @var int 栈顶指针
     */
    private $_stackTop;

    /**
     * @var int 栈的容量
     */
    private $_stackSize;

    /**
     * Stack constructor. 初始化栈
     * @param int $size 栈的容量大小;
     */
    public function __construct($size)
    {
        $this-_stack = [];
        $this-_stackSize = $size;

        /**
         * 栈顶初始状态位于栈底
         */
        $this-_stackTop = self::TOP_INIT;
    }

    /**
     * @method 销毁栈(非必需)
     */
    public function __destruct()
    {
        unset($this-_stack);
    }

    /**
     * @method 入栈
     * @param mixed $elem 入栈元素
     * @return bool
     */
    public function push($elem)
    {
        if ($this-isFull()) {
            return false;
        }
        $this-_stack[++$this-_stackTop] = $elem;
        return true;
    }

    /**
     * @method 出栈
     * @return mixed|null 返回栈顶的元素或者当栈为空时返回null
     */
    public function pop()
    {
        if ($this-isEmpty()) {
            return null;
        }
        $result = $this-_stack[$this-_stackTop];
        unset($this-_stack[$this-_stackTop]);
        $this-_stackTop--;
        return $result;
    }

    /**
     * @method 判断栈是否为空;
     * @return bool
     */
    public function isEmpty()
    {
        return $this-_stackTop === self::TOP_INIT;
    }

    /**
     * @method 判断栈是否达到最大;
     * @return bool
     */
    public function isFull()
    {
        return $this-_stackSize - 1 === $this-_stackTop;
    }

    /**
     * @method 清空栈
     */
    public function clearStack()
    {
        $this-_stack = [];
        $this-_stackTop = self::TOP_INIT;
    }

    /**
     * @method 遍历栈(测试用);
     */
    public function outputStack()
    {
        echo ‘take traversal stack from bottom to top‘.PHP_EOL;
        for ($i = self::BOTTOM; $i  $this-_stackTop + 1; $i++) {
            echo $this-_stack[$i].PHP_EOL;
        }
        echo PHP_EOL;
        echo PHP_EOL;
        echo ‘take traversal stack from top to bottom‘.PHP_EOL;
        for ($i = $this-_stackTop; $i = self::BOTTOM; $i--) {
            echo $this-_stack[$i].PHP_EOL;
        }
    }
}

测试一下栈操作类

$s = new Stack(4);

$s-push(1);
$s-push(2);
$s-push(3);
$s-push(4);
$s-push(5);
$s-outputStack();  //stack from top to bottom: 4 3 2 1
$s-pop();          //output:4  stack: 3 2 1
$s-pop();          //output:3  stack: 2 1
$s-outputStack();  //stack: 2 1
$s-push(5);
$s-outputStack();  //stack: 5 2 1
$s-clearStack();
var_dump($s-pop());    //null;

经过测试代码很讲道理;

如有不对,敬请指教

数据结构随笔-php实现栈

原文地址:http://www.cnblogs.com/nerd-gordon/p/7294581.html


最新回复(0)
/jishus5QZ_2B_2BEyOVifvd9qSWFMuCKC7gQUlHYWkK216Q_3D_3D4719057
8 简首页