数据结构之php实现栈
0 / 2 / 创建于 4年前 /
thinkabel 的个人博客
在上一次的文章中, 我们介绍了数组, 在讲解数组的过程中, 也提到了一点, 就是数组是线性结构。在今天的文章里，栈也是属于线性结构，我们先看下定义。
一、概念
那什么是栈呢? 我们一起来看下定义:
堆栈（英语：stack）又称为栈或堆叠，是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。
维基百科
栈是一种先进先出的线性数据结构（FIFO), 在计算机的世界里, 栈拥有着不可思议的作用。比如我们在编写文章时, 作图时, 写代码时 等等, 所使用的的 Undo (撤销) 操作, 就是使用这种数据结构进行实现的。先来看下栈在计算机中是什么“模样”.
(栈的结构图)
二、栈的应用
无处不在的 Undo 操作
比如 我现在输入 沉迷 学习 无法 自拔 这几个词, 我输入 学习, 这个动作 就会被编译机器中的栈给记录下来。这个时候我想输入，无法， 不小心打错了，输入了 “无非是”， 这个动作同样会被栈记录下来 – 入栈，在你意识到自己打错了，想撤销这个操作的时候，这个时候，打错的这个“无非是”就会被栈 “出栈”。我们看下流程图
程序调用的系统栈
还有在我们写代码的时候，经常会遇到，当前方法，访问 另一个方法的情况，那程序是怎么知道跳转方法执行完了之后，该回到哪个方法呢？我们一起来看下流程图。
刚开始，进入 A 方法， 程序往下执行，开始访问B方法，这个时候 是在方法 A 的第二行执行B方法的，这是将 A2 压入 栈中，然后执行 B 方法， 在 B 方法中， 又执行了 C 方法， 这时候，将 B2 压入栈中。
程序 C 执行完后，访问栈顶的元素，是 B2， 这时返回 B 方法 中的第二行继续执行，B2 进行 出栈， 直至程序执行完毕
三、代码实现
ArrayStructure.php
<?php
class ArrayStructure
{
// 数组实际元素
private $size = 0;
// 数组的容量大小
private $capacity = 0;
// 用于存放数据
private $data = [];
/**
* ArrayStruct constructor.
*
* @param int $capacity 数组容量大小
*/
public function __construct($capacity = 10)
{
$this->capacity = $capacity;
}
/**
* Notes: 获取数组实际元素个数
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 15:12
*
* @return int
*/
public function getSize(): int
{
return $this->size;
}
/**
* Notes: 扩容
* User: think abel
* Date: 2021/1/10 0010
* Time: 17:08
*
* @param $factor
*/
protected function resize($factor)
{
$this->capacity = $factor * $this->capacity;
}
/**
* Notes: 获取数组的容量
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 15:14
*
* @return int
*/
public function getCapacity(): int
{
return $this->capacity;
}
/**
* Notes: 数组是否为空
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 15:16
*
* @return bool
*/
public function isEmpty(): bool
{
return $this->size === 0;
}
/**
* Notes: 往数组指定位置插入数据
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 15:27
*
* @param int $index 需要插入的下标/索引
* @param int $ele 需要插入的元素
*/
public function add(int $index, $ele): void
{
// 如果当前的实际大小 等于 当前容量, 则不可以进行插入
try {
if ($this->size === $this->capacity) {
throw new Exception("添加失败, Array 已经到达最大容量");
}
if ($index < 0 || $index > $this->size) {
throw new Exception("添加失败, index require >= 0 and <= " . $this->size);
}
/**
* 从最后一个元素开始进行遍历, 直到下标 为 当前输入的 下标, 终止
* 每次将当前遍历的数值 往后 移动一位
*/
for ($i = $this->size - 1; $i >= $index; $i --) {
$this->data[$i + 1] = $this->data[$i];
}
// 目前当前下标还是存在之前的元素, 因为当前元素已经移动到后面一位, 所以直接覆盖就好
$this->data[$index] = $ele;
// 维护当前实际大小
$this->size ++;
}
catch (Exception $e) {
echo $e->getMessage();
}
}
/**
* Notes: 向所有元素后添加一个元素
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 15:19
*/
public function addLast($element): void
{
$this->add($this->size, $element);
}
/**
* Notes: 向第一位添加一个元素
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 15:19
*/
public function addFirst(int $element): void
{
$this->add(0, $element);
}
/**
* Notes: 数组转字符串
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 15:50
*
* @return string
*/
public function toString(): string
{
$str = 'Array: size = ' . $this->size . ',' . 'capacity = ' . $this->capacity . PHP_EOL;
$str .= '[';
for ($i = 0; $i < $this->size; $i ++) {
$str .= $this->data[$i];
if ($i != $this->size - 1) {
$str .= ',';
}
}
$str .= ']';
return $str . PHP_EOL;
}
/**
* Notes: 获取指定下标位置的元素
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 16:13
*
* @param int $index
*
* @return int
*/
public function get($index)
{
try {
if ($index < 0 || $index >= $this->size) {
throw new Exception("获取失败, index require >= 0 and < " . $this->size);
}
return $this->data[$index];
}
catch (Exception $e) {
return $e->getMessage();
}
}
/**
* Notes: 获取最后一个
* User: think abel
* Date: 2021/1/10 0010
* Time: 15:48
*
* @return int
*/
public function getLast()
{
return $this->get($this->size - 1);
}
/**
* Notes: 获取第一个
* User: think abel
* Date: 2021/1/10 0010
* Time: 15:48
*
* @return int
*/
public function getFirst()
{
return $this->get(0);
}
/**
* Notes: 修改指定下标位置的元素为 ele
* User: think abel
* Date: 2021/1/9 0009
* Time: 12:04
*
* @param int $index
* @param int $ele
*
* @return string
*/
public function set(int $index, int $ele)
{
try {
if ($index < 0 || $index >= $this->size) {
throw new Exception("获取失败, index require >= 0 and < " . $this->size);
}
$this->data[$index] = $ele;
}
catch (Exception $e) {
return $e->getMessage();
}
}
/**
* Notes: 删除指定位置上的元素
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 16:19
*
* @param int $index
*
* @return int|string
*/
public function remove(int $index): int
{
try {
if ($index < 0 || $index >= $this->size) {
throw new Exception("移除失败, index require >= 0 and < " . $this->size);
}
$return = $this->data[$index];
for ($i = $index + 1; $i < $this->size; $i ++) {
$this->data[$i - 1] = $this->data[$i];
}
$this->size --;
return $return;
}
catch (Exception $e) {
return $e->getMessage();
}
}
/**
* Notes: 删除第一个
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 16:39
*
* @return int
*/
public function removeFirst(): int
{
try {
return $this->remove(0);
}
catch (Exception $e) {
return $e->getMessage();
}
}
/**
* Notes: 删除最后一个
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 16:39
*
* @return int
*/
public function removeLast()
{
try {
return $this->remove($this->size - 1);
}
catch (Exception $e) {
return $e->getMessage();
}
}
/**
* Notes: 如果有元素, 就删除
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 16:44
*
* @param int $ele
*
* @return bool
*/
public function removeElement(int $ele): bool
{
$index = $this->find($ele);
if ($index != - 1) {
$this->remove($index);
}
}
/**
* Notes: 是否包含元素
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 16:22
*
* @param int $ele
*
* @return bool
*/
public function contains(int $ele): bool
{
for ($i = 0; $i < $this->size; $i ++) {
if ($this->data[$i] == $ele) {
return true;
}
}
return false;
}
/**
* Notes: 获取当前元素的索引
* Author: PhpStorm
* Date: 2021/1/8 0008
* Time: 16:22
*
* @param int $ele
*
* @return int
*/
public function find(int $ele): int
{
for ($i = 0; $i < $this->size; $i ++) {
if ($this->data[$i] == $ele) {
return $i;
}
}
return - 1;
}
}Stack.php
interface Stack
{
public function getSize();
public function isEmpty();
public function push($element);
public function pop();
public function top();
}ArrayStack.php
<?php
/**
* Created by : PhpStorm
* User: think abel
* Date: 2021/1/10 0010
* Time: 15:33
*/
include 'Stack.php';
include 'ArrayStructure.php';
class ArrayStack implements Stack
{
private $array;
public function __construct(int $capacity = 10)
{
$this->array = new ArrayStructure($capacity);
}
public function getSize()
{
return $this->array->getSize();
}
public function isEmpty()
{
return $this->array->isEmpty();
}
public function getCapacity()
{
return $this->array->getCapacity();
}
public function push($element)
{
$this->array->addLast($element);
}
public function pop()
{
return $this->array->removeLast();
}
public function top()
{
return $this->array->getLast();
}
public function toString(): string
{
$str = "Stack: [";
for ($i = 0; $i < $this->array->getSize(); $i ++) {
$str .= $this->array->get($i);
if ($i != $this->array->getSize() - 1) {
$str .= ", ";
}
}
$str .= "] top";
return $str;
}
}
四、简单复杂度分析
O: 描述是算法的运行时间 和 输入数据之间的关系 — 程序运行时间 和 数数据 成线性关系 O(n)
ArrayStack
push(e) O(1) // 如果是触发了扩容, 通过均摊复杂度来分析的话,依然是O(1)
pop() O(1) // 如果是触发了扩容, 通过均摊复杂度来分析的话,依然是O(1)
top() O(1)
getSize() O(1)
isEmpty(1) O(1)仓库地址
仓库地址: gitee.com/thinkAbel/data-structure
最后祝大家 工作开心, 永不加班
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
array_pusharray_pop就完事了栈是一种先进先出的线性数据结构（FIFO)这里写错了吧