PHP의 스택에 대한 자세한 설명

논리적 구조의 경우에도 가장 간단한 것부터 시작합니다. 스택과 큐는 대부분의 사람들에게 친숙한 단어이지만, 힙과 스택은 실제로는 다른 두 가지입니다. 면접 시 면접관의 말에 당황하지 마세요. 힙은 트리 구조 또는 완전한 이진 트리 구조입니다. 오늘은 주로 이 스택의 적용에 대해 이야기하겠습니다.

스택이란 무엇인가요?

스택은 일반적으로 순차 데이터 구조입니다. 가장 큰 특징은 LIFO(후입선출), 또는 반대로 FILO(선입선출)입니다. 이 두 문장은 무엇을 의미하나요? 가장 전형적인 예는 TV 시리즈, 특히 총격전 영화를 볼 때 누구나 확실히 보게 될 것입니다. 바로 잡지입니다.

탄창을 장전할 때는 탄알을 하나씩 탄창에 밀어넣는 것입니다. 즉, 첫 번째 총알은 아래쪽에서 누르고, 사격할 때는 탄창의 위쪽으로 총알을 밀어넣습니다. 발사되며, 첫 번째로 넣은 총알이 마지막으로 발사됩니다.

이 예는 실제로 매우 생생합니다. 용어를 통일합시다. 탄창에 총알을 누르는 것을 "스택"이라고 하며, 첫 번째 총알이 아래쪽에 있고, 이 위치를 "스택 하단"이라고 하며, 마지막 총알이 상단에 있고, 이 위치를 "스택 상단"이라고 합니다. 발사됨 스택의 "상단"에 있는 총알입니다. 이 작업을 "팝핑"이라고 합니다.

위 용어의 정의를 통해 스택의 논리 연산은 주로 "스택 내부"와 "스택 외부"임을 알 수 있으며, 논리 구조에서 가장 주의해야 할 점은 " 스택 상단" 및 "스택 하단". 스택을 팝하고 팝할 때의 상태입니다. 물론, 스택의 논리적 구조의 순서나 체인 구조를 사용해도 문제는 없다.

순차 스택

우선, 순차 스택을 비교적 간단하게 구현한 것입니다. 순차구조이므로 배열을 사용합니다. 하지만 "스택 상단"이나 "스택 하단"의 상황도 기록해야 하므로 순차 스택의 배열을 클래스로 캡슐화합니다.

동시에 이 클래스의 속성을 정의하여 현재 스택의 "상단" 또는 "하단" 포인터를 나타냅니다. 이는 실제로 배열에서 현재 "상단" 또는 "하단"의 아래 첨자 위치입니다. 일반적으로 말하면 "스택의 상단" 위치만 기록하고 기본적으로 "스택의 하단"을 -1로 설정하면 됩니다. 배열 첨자 자체가 0부터 시작하기 때문에 "스택 상단" 속성이 -1이면 스택은 "상단"과 "하단"이 함께 있고 그 안에 요소가 없기 때문에 빈 스택입니다.

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

빈 배열을 사용하고 $top을 -1로 설정하면 순차 스택을 초기화하는 것이 간단합니다.

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

다음 단계는 "푸시" 및 "팝" 작업입니다. 먼저 코드를 살펴보겠습니다.

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;
}

스택에 푸시하는 것은 매우 간단합니다. 배열 요소에 콘텐츠를 추가한 다음 $top++하면 됩니다. 하지만 C 언어라면 배열 길이 제한이 있기 때문에 스택에 push할 때 스택이 꽉 찼는지 여부도 확인해야 합니다. 물론 PHP에서는 이런 걱정이 없습니다.

순차 스택 푸시 아이콘

스택을 팝할 때 현재 스택이 비어 있는지 확인해야 합니다. 이는 언어를 구분하지 않습니다. 왜냐하면 이 스택이 -1보다 작으면 이 스택을 다시 사용하면 문제가 발생하기 때문입니다. 잘못된. 스택을 팝할 때 스택이 이미 비어 있으면 $top--를 제공하지 말고 스택의 최상위 요소를 가져와 반환하면 됩니다.

순차 스택 팝핑 아이콘

이 순차 스택의 테스트 결과를 살펴보겠습니다.

$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)
//   }

어레이를 통해 스택을 조작하는 방법이 참 간단하지 않나요? 체인 스택을 읽고 학습한 후, PHP가 우리를 위해 준비한 배열 스택 작업 기능에 대해 이야기해 보겠습니다.

Chain Stack

사실 체인 저장 구조의 경우 핵심 내용은 여전히 ​​동일합니다. 스택 상단에도 신경 써야 하고, 스택 안팎의 작업에도 신경 써야 합니다. . 그러나 체인에서는 헤드 삽입을 사용할 수 있습니다. 즉, 삽입된 데이터를 체인 상단에 유지하여 "스택 상단" 효과를 얻을 수 있습니다. 이런 방식으로 스택의 현재 최상위 위치를 저장하기 위해 특별한 속성이 필요하지 않습니다. 다이어그램을 통해 직접적으로 이해하는 것이 더 명확해질 것입니다.

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

데이터의 구조는 그냥 일반적인 체인 구조입니다. 중요한 것은 푸시 작업이 어떻게 수행되는지 보는 것입니다.

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;
}

사실 체인스택에서 빈스택을 초기화하는 작업은 별 의미가 없습니다. null 변수를 직접 정의하고 이에 대한 체인 작업을 수행할 수 있지만 여기서는 여전히 순차 스택과의 통합이 유지됩니다. 순차 스택의 스택 맨 아래가 -1인 것처럼 체인 스택에서도 스택 맨 아래가 null 개체 노드라는 데 동의합니다.

接下来就是入栈操作了。这里我们使用的是头插法，其实就是将新元素放到链表的顶端。先实例化一个节点，然后将这个节点的 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视频教程

위 내용은 PHP의 스택에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!