数据结构与算法(四)栈

代码位置:Github

什么是栈

栈是一种和列表类似的数据结构,它操作高效,因为它只允许从栈顶操作数据,而且只有入栈、出栈两种重要的操作方式。

在生活中,它的结构就像是用来装羽毛球的球桶,入口与出口是同一个,假设有五只羽毛球和一个球桶,如果想要把羽毛球都装进球桶里,那就一只一只地装进去,这时候我们假设五只球的序号为:A、B、C、D、E,装进球桶的顺序就按照这个顺序去装。那么,等我们想打羽毛球的时候,我们从球桶中取出球的顺序就是:E、D、C、B、A,这个特性就是 LIFO(后进先出)。

数组和链表都能用来实现栈结构,用数组实现的栈又叫做顺序栈,用链表实现的栈叫做链式栈

栈的常用操作

  • 入栈
  • 出栈
  • 预览栈顶元素
  • 清空栈

入栈即为向栈内加入元素,出栈则相反,从栈内取出一个元素。无论是入栈还是出栈栈,顶指针都有会相应的变化。

用 PHP 实现栈

<?php

/**
 * Class Stack
 *
 * 栈
 */
class Stack
{
    /**
     * 用来存放栈内的数据
     *
     * @var array
     */
    private $data = [];

    /**
     * 栈顶指针
     *
     * @var int
     */
    private $top = 0;

    /**
     * 入栈操作
     *
     * @param $element
     */
    public function push($element)
    {
        $this->data[$this->top++] = $element;
    }

    /**
     * 出栈操作
     *
     * @return mixed
     */
    public function pop()
    {
        // 防止下标越界
        if ($this->top) {
            return $this->data[--$this->top];
        }

        return null;
    }

    /**
     * 查看栈顶元素
     *
     * @return mixed
     */
    public function peek()
    {
        return $this->data[$this->top - 1];
    }

    /**
     * 获取栈的大小
     *
     * @return int
     */
    public function length()
    {
        return $this->top;
    }

    /**
     * 清空栈
     */
    public function clear()
    {
        $this->data = [];
        $this->top = 0;
    }
}

这样就简单地实现了一个包含入栈、出栈、查看栈顶元素、获取栈的长度、清空栈等功能的栈结构。

因为栈顶指针指向的是下一个元素的位置,所以入栈操作后才把栈指针指增加。而入栈操作中,因为栈指针指向的位置并没有数据,所以需要先将栈指针减小,再取得这个减小后的栈指针的位置上的元素。

栈的使用场景

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该使用这种数据结构。

我们还可以使用它实现:

  • 判断字符串是否是回文
  • 模拟递归

回文

回文是指这样一种现象:一个单词、短语或数字,从前往后写和从后往前写都是一样的。比如:『上海自来水来自海上』、『山西运煤车煤运西山』等这样的字符串就是回文。

<?php

include '../common/Stack.php';

/**
 * 判断字符串是否为回文
 *
 * @param $string
 * @return bool
 */
function isPalindrome(string $string)
{
    $stack = new Stack();

    $length = mb_strlen($string);
    for ($i = 0; $i < $length; $i++) {
        $stack->push($string[$i]);
    }

    $revertString = '';
    while ($stack->length()) {
        $revertString .= $stack->pop();
    }

    return $string === $revertString;
}

递归

栈还可以用来模拟递归。假设我们计算 5 的阶乘,用递归实现代码如下:

/**
 * 递归计算一个数值的阶乘
 *
 * @param int $n
 * @return int
 */
function recursiveFactorial(int $n)
{
    if ($n === 0) {
        return 1;
    }

    return $n * recursiveFactorial($n - 1);
}

用栈模拟递归

/**
 * 用栈模拟递归进行阶乘运算
 *
 * @param int $n
 * @return int|mixed
 */
function stackFactorial(int $n)
{
    $stack = new Stack();

    $result = 1;

    while ($n > 1) {
        $stack->push($n--);
    }

    while ($stack->length()) {
        $result *= $stack->pop();
    }

    return $result;
}

 本篇
数据结构与算法(四)栈 数据结构与算法(四)栈
代码位置:Github 什么是栈栈是一种和列表类似的数据结构,它操作高效,因为它只允许从栈顶操作数据,而且只有入栈、出栈两种重要的操作方式。 在生活中,它的结构就像是用来装羽毛球的球桶,入口与出口是同一个,假设有五只羽毛球和一个球桶,如
2019-04-21
下一篇 
The Fucking Github The Fucking Github
The Fucking Github 是一个 Chrome 浏览器的扩展插件,可以用来很方便地查看、整理、搜索你已经 Star 过的项目和搜索 Github 上的项目。 能干啥你是否在 Github 上有很多 star 过的项目并且经常需
2019-04-14
  目录