### 一、栈
1）栈（Stack）是一种后进先出（LIFO）表，插入删除操作都只能在一个位置上进表，这个位置位于表的末端，叫做栈顶（Top），另一端则称为栈底（Bottom），又称为表头。

2）对栈的基本操作有push和pop，表示进栈和出栈，相当于插入和删除操作。存储数据时，先进入的数据被压入栈底，后进入的数据则在栈顶；读取数据时，从栈顶开始弹出数据。

![](https://blog.junphp.com/public/upload/20220309/be60666547dd3b419085df7b2f3b4529.png)

3）在PHP函数中，`array_push`函数是向数组尾部添加元素，即入栈操作；`array_pop`函数是删除数组尾部元素，即出栈操作。
```php
$array =  array('a', 'b');
array_push($array, 'c'); //入栈
array_pop($array);       //出栈
```

### 使用数组实现栈

选择用数组表示栈内容必须预先估计栈的最大容量。

因为数组一旦创建，其大小是无法改变的，而数组设置过大可能会浪费大量内存，设置过小又可能会溢出。

php用数组实现栈，需要实现以下方法支持：
```
1. getLength(): 获得栈的长度
2. push(): 入栈，在最顶层加入数据。
3. pop(): 出栈，返回并移除最顶层的数据。
4. getTop(): 返回最顶层数据的值，但不移除它
5. clearStack(): 清空栈
6. show(): 遍历栈元素
```
具体代码如下：`
```php
class Stack {
    // 使用数组实现栈结构
    public $stack = [];

// 获得栈的长度
 public function getLength() {
 return count($this->stack);
 }
 // 入栈，在最顶层加入数据。
 public function push($element) {
 $this->stack[] = $element;
 }
 // 出栈，返回并移除最顶层的数据。
 public function pop() {
 if ($this->getLength() > 0) {
 return array_pop($this->stack);
 }
 }
 // 返回最顶层数据的值，但不移除它
 public function getTop() {
 $top = $this->getLength() - 1;
 return $this->stack[$top];
 }
 // 清空栈
 public function clearStack() {
 $this->stack = [];
 }
 // 遍历栈元素
 public function show() {
 if ($this->getLength() > 0) {
 for ($i = 0; $i < $this->getLength(); $i++) {
 echo $this->stack[$i] . PHP_EOL;
 }
 } else {
 echo "空！";
 }
 }
}
// 测试
$s = new Stack();
$s->push('a');
$s->push('b');
$s->push('c');
echo "栈为：";
$s->show();
echo "";
echo '栈顶元素为：' . $s->getTop();
echo "";
echo '栈的长度为：' . $s->getLength();
echo "";
$s->pop();
echo "出栈，弹出c，栈为：";
$s->show();
echo "";
echo "清空栈，栈为：";
$s->clearStack();
$s->show();
```

### 使用链表实现栈
使用链表实现栈，需要实现以下几个方法：
```
1. isEmpty(): 判断队列是否为空。
2. push(): 入栈，插入新的栈顶节点
3. pop(): 出栈，删除栈顶元素
4. clear(): 清空栈
5. show(): 遍历栈元素
```
具体代码如下：
```php
// 节点类
class Node {
    public $data;   // 节点数据
    public $next;   // 下一节点

public function __construct($data) {
        $this->data = $data;
        $this->next = NULL;
    }
}
class Stack {
    private $header;        // 头节点

function __construct($data) {
        $this->header = new Node($data);
    }

// 判断栈是否为空
 public function isEmpty() {
 if (!empty($this->header) && $this->header->next !== null) { // 不为空
 return false;
 }
 return true;
 }
 // 入栈，插入新的栈顶节点
 public function push($element) {
 $newNode = new Node($element);
 $current = $this->header;
 if ($current->next == null) { // 只有头节点
 $this->header->next = $newNode;
 } else { // 遍历到栈尾最后一个元素
 while ($current->next != null) {
 $current = $current->next;
 }
 $current->next = $newNode;
 }
 $newNode->next = null;
 }
 // 出栈，删除栈顶元素
 public function pop() {
 if ($this->isEmpty()) { // 栈为空
 return false;
 }
 $current = $this->header;
 while ($current->next->next != null) {
 $current = $current->next;
 }
 $current->next = null;
 }
 // 清空栈
 public function clear() {
 $this->header = null;
 }
 // 显示栈中的元素
 public function show() {
 $current = $this->header;
 if ($this->isEmpty()) {
 echo "空！";
 } else {
 while ($current->next != null) {
 echo $current->next->data . PHP_EOL;
 $current = $current->next;
 }
 }
 }
}
// 测试
$s = new Stack('header');
$s->push('a');
$s->push('b');
$s->push('c');
echo "栈为：";
$s->show();
echo "";
$s->pop();
echo "出栈，弹出c，栈为：";
$s->show();
echo "";
echo "清空栈，栈为：";
$s->clear();
$s->show();
```

### 栈和队列的区别
栈的插入和删除操作都是在一端进行的，而队列的操作却是在两端进行的。

栈是先进后出，队列是先进先出。

栈只允许在表尾一端进行插入和删除，队列只允许在表尾一端进行插入，在表头一端进行删除。

已有0条评论

添加新评论☺

如果认为本文对您有所帮助请赞助本站

支付宝扫一扫赞助

已有0条评论

添加新评论☺