特殊的线性表 - 栈

Thursday. March 28, 2019 - 4 mins

数据结构与算法系列（五）

前面我们聊了两种基本的数据结构 —— 数组和链表，从逻辑角度来说，它们都是线性结构（就是排成一条线的结构，只有前后两个方向，非线性结构包括树、图等，后面会讲到），从存储角度来说，一个是顺序存储，一个是链式存储，各有利弊，数组需要预先申请连续内存，超出限制会溢出，但是对明确知道规模的小型数据集而言，使用数组会更加高效，随机访问的特性也更加方面数组读取，但插入和删除性能要差一些；链表的话没有空间限制，但是需要额外空间存储指针，插入、删除效率很高，但不支持随机访问。虽说 PHP 中很少接触到这些，但是你学习使用 C 语言的话这些基础还是需要了解的。接下来我们要介绍两种特殊的线性结构，或者说用于满足特定场景需求的线性结构：栈和队列。首先来看栈。

栈又叫堆栈，是限定只能在一端进行插入和删除操作的线性表，并且满足先进后出，后进先出的特点。我们把允许插入和删除的一端叫做栈顶，另一个端叫做栈底，不含任何数据的栈叫做空栈。

栈支持通过数组/链表实现，通过数组实现的通常叫做顺序栈，通过链表实现的叫做链栈。由于是在 PHP 中演示，我尽量偏向 PHP 语言，化繁就简，下面我们简单演示下如何在 PHP 中通过数组实现一个简单的顺序栈：

  <?php

/**
 * 通过 PHP 数组实现简单的顺序栈
 */
class SimpleStack {

    private $_stack = [];
    private $_size = [];

    public function __construct($size = 10)
    {
        $this->_size = $size;
    }

    // 获取栈顶元素
    public function pop()
    {
        // 空栈
        if (count($this->_stack) == 0) {
            return false;
        }
        return array_pop($this->_stack);
    }

    // 推送元素到栈顶
    public function push($value)
    {
        // 满栈
        if (count($this->_stack) == $this->_size) {
            return false;
        }
        array_push($this->_stack, $value);
        return true;
    }

    public function isEmpty()
    {
        // 是否是空栈
        return current($this->_stack) == false;
    }

    public function size()
    {
        return count($this->_stack);
    }
}

$stack = new SimpleStack(15);
var_dump($stack->isEmpty());  # true
$stack->push(111);
$stack->push('holle');
var_dump($stack->pop());  # holle
var_dump($stack->size());  # 1

在 PHP 底层 SPL 库中也提供了堆栈的实现类 SplStack，堆栈的概念比较简单，理解起来也不复杂，下面给出一个图示，帮助你形象了解栈的操作流程

SplStack extends SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {
    /* 方法 */
    __construct ( void )
    setIteratorMode ( int $mode ) : void
    /* 继承的方法 */
    public SplDoublyLinkedList::add ( mixed $index , mixed $newval ) : void
    public SplDoublyLinkedList::bottom ( void ) : mixed
    public SplDoublyLinkedList::count ( void ) : int
    public SplDoublyLinkedList::current ( void ) : mixed
    public SplDoublyLinkedList::getIteratorMode ( void ) : int
    public SplDoublyLinkedList::isEmpty ( void ) : bool
    public SplDoublyLinkedList::key ( void ) : mixed
    public SplDoublyLinkedList::next ( void ) : void
    public SplDoublyLinkedList::offsetExists ( mixed $index ) : bool
    public SplDoublyLinkedList::offsetGet ( mixed $index ) : mixed
    public SplDoublyLinkedList::offsetSet ( mixed $index , mixed $newval ) : void
    public SplDoublyLinkedList::offsetUnset ( mixed $index ) : void
    public SplDoublyLinkedList::pop ( void ) : mixed
    public SplDoublyLinkedList::prev ( void ) : void
    public SplDoublyLinkedList::push ( mixed $value ) : void
    public SplDoublyLinkedList::rewind ( void ) : void
    public SplDoublyLinkedList::serialize ( void ) : string
    public SplDoublyLinkedList::setIteratorMode ( int $mode ) : void
    public SplDoublyLinkedList::shift ( void ) : mixed
    public SplDoublyLinkedList::top ( void ) : mixed
    public SplDoublyLinkedList::unserialize ( string $serialized ) : void
    public SplDoublyLinkedList::unshift ( mixed $value ) : void
    public SplDoublyLinkedList::valid ( void ) : bool
}

Demo:

<?php
//SplStack Mode is LIFO (Last In First Out)
  
$q = new SplStack();

$q[] = 1;
$q[] = 2;
$q[] = 3;
$q->push(4);
$q->add(4,5);

$q->rewind();
while($q->valid()){
    echo $q->current(),"\n";
    $q->next();
}
?>

Output
5
4
3
2
1

堆栈在日常开发和软件使用中，应用非常广泛，比如我们的浏览器前进、倒退功能，编辑器/IDE 中的撤销、取消撤销功能，程序代码中的函数调用、递归、四则运算等等，都是基于堆栈这种数据结构来实现的，就连著名的 stackoverflow 网站也是取「栈溢出」，需要求教之意.

特殊的线性表 - 栈

数据结构与算法系列（五）

Related Posts