Detailed explanation of stack in php

For the logical structure, we also start from the simplest one. Stack and queue are familiar words to most people, but heap and stack are actually two different things. Don't be confused by the interviewer during the interview. The heap is a tree structure, or a complete binary tree structure. Today, we are mainly talking about the application of this stack.

What is a stack?

The stack is generally a sequential data structure. Its biggest feature is last-in-first-out (LIFO), or conversely, first-in-first-out (FILO). What do these two sentences mean? The most typical example is something that everyone will definitely see when watching TV series, especially gun fight movies: magazines.

When loading the magazine, the bullets are pressed into the magazine one by one. In other words, the first bullet is pressed at the bottom, and when firing, the bullets are pressed into the magazine one by one. The bullet is ejected from the top of the magazine in reverse order, with the first bullet inserted being the last to be ejected.

This example is actually very vivid, let’s unify the terminology. Pressing the bullet into the magazine is called "stacking", the first bullet is at the bottom, this position is called the "stack bottom", the last bullet is at the top, this position is called the "stack top", the bullet fired It is the bullet on the "top" of the stack. This operation is called "popping".

Through the definitions of the above terms, we can see that the logical operations of the stack are mainly "into the stack" and "out of the stack", and the most important thing to care about in the logical structure is the "top of the stack" and "top of the stack" "Bottom" state when popping or pushing the stack. Of course, there is no problem in using the order or chain structure of the stack's logical structure. Let's look at it one by one.

Sequential Stack

First of all, it is a relatively simple implementation of the sequential stack. Since it is a sequential structure, then use an array. However, we also need to record the situation of the "top of the stack" or the "bottom of the stack", so we encapsulate the array of the sequential stack into a class.

At the same time, define an attribute in this class to indicate the "top" or "bottom" pointer of the current stack, which is actually the subscript position of the current "top" or "bottom" in the array. . Generally speaking, we only need to record the position of the "top of the stack" and set the "bottom of the stack" to -1 by default. Because the array subscript itself starts from 0, when the "top of stack" attribute is -1, the stack is an empty stack, because its "top" and "bottom" are together and there are no elements in it.

class SqStack
{
    public $data;
    public $top;
}

Initializing the sequential stack is simple, an empty array and setting $top to -1 .

function InitSqStack()
{
    $stack = new SqStack();
    $stack->data = [];
    $stack->top = -1;
    return $stack;
}

The next step is the "push" and "pop" operations. Let's look at the code first.

function PushSqStack(SqStack &$stack, $x){
    $stack->top ++;
    $stack->data[$stack->top] = $x;
}

function PopSqStack(SqStack &$stack){
    // 栈空
    if($stack->top == -1){
        return false;
    }

    $v = $stack->data[$stack->top];
    $stack->top--;
    return $v;
}

Pushing onto the stack is very simple, just add content to the array elements and then $top. However, if it is C language, because it has an array length limit, when pushing onto the stack, we also need to determine whether the stack is full. Of course, in PHP we don't have this concern.

Sequential stack push icon

#When popping the stack, you need to determine whether the current stack is empty. This does not distinguish between languages, because If it is smaller than -1, problems will occur when using this stack again. When popping the stack, if the stack is already empty, don't give $top--, then just get the top element of the stack and return it.

Sequential stack popping icon

#Let’s take a look at the test results of this sequential stack.

$stack = InitSqStack();

PushSqStack($stack, 'a');
PushSqStack($stack, 'b');
PushSqStack($stack, 'c');

var_dump($stack);
// object(SqStack)#1 (2) {
//     ["data"]=>
//     array(3) {
//       [0]=>
//       string(1) "a"
//       [1]=>
//       string(1) "b"
//       [2]=>
//       string(1) "c"
//     }
//     ["top"]=>
//     int(2)
//   }

echo PopSqStack($stack), PHP_EOL; // c
echo PopSqStack($stack), PHP_EOL; // b
echo PopSqStack($stack), PHP_EOL; // a

var_dump($stack);
// object(SqStack)#1 (2) {
//     ["data"]=>
//     array(3) {
//       [0]=>
//       string(1) "a"
//       [1]=>
//       string(1) "b"
//       [2]=>
//       string(1) "c"
//     }
//     ["top"]=>
//     int(-1)
//   }

Is it very simple to operate the stack through an array? After reading and learning the chain stack, we will also talk about the array stack operation functions that PHP has prepared for us, which will be more convenient to use.

Chain Stack

In fact, for the chain storage structure, the core content is still the same. We also need to care about the top of our stack, and we also need to care about the operations in and out of the stack. However, in the chain, we can use head insertion, that is, keeping the inserted data at the top of the chain to achieve the "top of stack" effect. In this way, we don't need a special attribute to save the current top position of the stack. It will be clearer to understand directly through a diagram.

class LinkStack{
    public $data;
    public $next;
}

The data structure is just a typical chain structure. The main thing is to see how the push operation is performed.

function InitLinkStack(){
    return null;
}

function PushLinkStack(?LinkStack &$stack, $x){
    $s = new LinkStack();
    $s->data = $x;
    $s->next = $stack;
    $stack = $s;
}

function PopLinkStack(?LinkStack &$stack){
    if($stack == NULL){
        return false;
    }
    $v = $stack->data;
    $stack = $stack->next;
    return $v;
}

In fact, the operation of initializing the empty stack in the chain stack has little meaning. We can directly define a null variable and perform chain operations on it, but here we still remain unified with the sequential stack. Just like the bottom of the stack in the sequential stack is -1, in the chain stack, we also agree that the bottom of the stack is a null object node.

接下来就是入栈操作了。这里我们使用的是头插法，其实就是将新元素放到链表的顶端。先实例化一个节点，然后将这个节点的 next 指向链表的头节点。接着再让当前这个节点成为链表的新的头节点，就像下图所示的那样。

同理，出栈的操作其实也是类似的，将头节点变成当前头节点的 next 节点，直到当前节点变成 null ，也就是栈已经空了，如图所示：

最后，我们同样的测试一下这一套链式栈的代码运行情况如何。

$stack = InitLinkStack();

PushLinkStack($stack, 'a');
PushLinkStack($stack, 'b');
PushLinkStack($stack, 'c');

var_dump($stack);
// object(LinkStack)#3 (2) {
//     ["data"]=>
//     string(1) "c"
//     ["next"]=>
//     object(LinkStack)#2 (2) {
//       ["data"]=>
//       string(1) "b"
//       ["next"]=>
//       object(LinkStack)#1 (2) {
//         ["data"]=>
//         string(1) "a"
//         ["next"]=>
//         NULL
//       }
//     }
//   }

echo PopLinkStack($stack), PHP_EOL; // c
echo PopLinkStack($stack), PHP_EOL; // b
echo PopLinkStack($stack), PHP_EOL; // a

var_dump($stack);
// NULL

是不是很多小伙伴已经看出之前我们花费了 4 篇文章的时间来讲述线性结构中的顺序表和链表的重要作用了吧。它们真的是一切其它逻辑结构的基础。不光是栈，在队列、树、图中我们都会有不同结构的线性和链式的实现。当然，更重要的是能体会它们之间的区别，在不同的业务场景中，两种不同的存储结构可能真的会带来完全不一样的体验。

PHP 为我们提供的数组栈操作

最后，我们简单的看一下在 PHP 中已经为我们准备好的两个数组操作函数。有了它们，对于顺序栈来说，我们的操作可以简化到非常傻瓜智能的效果。

$sqStackList = [];

array_push($sqStackList, 'a');
array_push($sqStackList, 'b');
array_push($sqStackList, 'c');

print_r($sqStackList);
// Array
// (
//     [0] => a
//     [1] => b
//     [2] => c
// )

array_pop($sqStackList);
print_r($sqStackList);
// Array
// (
//     [0] => a
//     [1] => b
// )

echo count($sqStackList) > 0 ? $sqStackList[count($sqStackList) - 1] : false, PHP_EOL;
// b

array_pop($sqStackList);

echo count($sqStackList) > 0 ? $sqStackList[count($sqStackList) - 1] : false, PHP_EOL;
// c

array_pop($sqStackList);

print_r($sqStackList);
// Array
// (
// )

估计不少同学早就用过这两个函数了。array_push() 就是向数组中压入一个数据，其实说白了，增加一个数据到数组中而已，没什么特别稀罕的功能。而 array_pop() 则是将数组最后一个位置的数据弹出。是不是和我们上面自己实现的那个顺序栈是完全相同的概念。没错，既然语言环境已经为我们准备好了，那么除了在某些场景下需要链式结构的话，大部分情况下我们直接使用这两个函数就可以方便地实现 PHP 中的栈操作了。

总结

栈这个逻辑结构是不是非常的简单清晰呀，在日常应用中其实栈的使用非常广泛。比如算式中的前缀算式、中缀算式、后缀算式的转化，比如我们后面学习树、图时要接触到了BFS（深度搜索），再根据BFS引出递归这个概念。另外，在解析字符时的一些对称匹配、回文算法的判断等等，这些都是栈的典型应用。可以说，栈这个东西撑起了计算机算法的半壁江山。而另外半壁呢？当然就是我们下回要讲的：队列。

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.栈和队列/source/3.1栈的相关逻辑操作.php

推荐学习：php视频教程

The above is the detailed content of Detailed explanation of stack in php. For more information, please follow other related articles on the PHP Chinese website!