数据结构之php实现栈
在上一次的文章中,我们介绍了数组,在讲解数组的过程中,也提到了一点,就是数组是线性结构。在今天的文章里,栈也是属于线性结构,我们先看下定义。
一、概念
那什么是栈呢?我们一起来看下定义:
堆栈(英语: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 协议》,转载必须注明作者和本文链接
推荐文章: