스택 및 큐 사용에 대한 올바른 자세(예제 포함)

스택과 큐에 대한 연구를 통해 우리는 데이터 구조가 실제로 매우 간단하다는 것을 느끼는 것 같습니다. 물론 이것은 시작에 불과합니다. 시퀀스 목록과 연결 목록에서 시작해 실제로 미래를 위한 길을 닦고 있는 현재 스택과 큐에 이르기까지 말이죠. 스택과 큐는 트리 및 그래프 순회 알고리즘에서 볼 수 있습니다. 여기서는 먼저 스택과 큐의 실제 적용 사례를 간략하게 살펴보겠습니다.

회문 질문

텍스트가 있다고 가정하고, 그것이 "회문"(후이 형제가 쓴 텍스트가 아님)인지 확인해야 합니다. 스택을 사용하여 이 문제를 해결할 수 있습니다.

회문이란 텍스트를 두 부분으로 나눈 후 이전 단락의 내용과 다음 단락의 내용이 완전히 동일하지만 순서가 반대라는 의미입니다. 예를 들어, 그것은 매우 유명합니다. 상하이의 수돗물은 바다에서 나옵니다. 상하이는 바다에서 유래합니다. 이 두 부분으로 구성된 구조는 한 문장으로 회문을 형성합니다. 또 다른 예는 짝수 길이의 문자(abcddcba)이며, 이 문자도 회문입니다.

비슷한 질문은 실제로 간단한 알고리즘 인터뷰 질문에 쉽게 나타날 수 있습니다. 많은 친구들이 이미 그것을 알아냈다고 생각합니다. 문단의 첫 번째 절반을 스택에 넣은 다음 두 번째 문단에서 하나씩 꺼내볼 수 있습니다. 세그먼트를 비교하면 현재 문자열이 회문인지 여부를 확인할 수 있습니다. 연습하지 않고 말로만 하지 말고, 코드를 구현해 봅시다.

$string1 = 'abcdedcba';
$string2 = 'abcdeedcba';
$string3 = 'abcdefcba';

function getIsPlalindrome($string)
{
    if (gettype($string) != 'string') {
        return false;
    }
    $strlen = strlen($string);
    $mid = floor($strlen / 2);
    $arr = [];

    if ($strlen < 2) {
        return false;
    }

    // 入栈
    for ($i = 0; $i < $mid; $i++) {
        array_push($arr, $string[$i]);
    }

    $j = $mid;
    $i = $strlen % 2 == 0 ? $mid : $mid + 1; // $i 从中位数开始
    for (; $i < $strlen; $i++) {
        $v = $arr[$j - 1]; // 获得栈顶元素
        if ($v != $string[$i]) {
            return false;
        }
        array_pop($arr); // 弹出栈顶元素
        $j--;
    }
    if ($arr) {
        return false;
    }
    return true;
}

var_dump(getIsPlalindrome($string1)); // bool(true)
var_dump(getIsPlalindrome($string2)); // bool(true)
var_dump(getIsPlalindrome($string3)); // bool(false)

매우 간단합니다. array_push() 및 array_pop()을 사용하여 순차 스택 작업을 수행하면 됩니다. 주목해야 할 유일한 점은 다양한 홀수 문자 길이와 짝수 문자 길이에 대해 우리가 원하는 중앙값도 그에 따라 변경된다는 것입니다.

회문 알고리즘은 비교적 간단합니다. 그 밖에도 자주 등장하는 단순 괄호 매칭, 산술 연산, 접미사 대 접미사 표현 등의 질문은 전형적인 스택 알고리즘 면접 질문입니다. 관련 콘텐츠를 검색해 직접 체험해 볼 수 있습니다.

Recursion

재귀에 대해 이야기하기 전에 한 가지를 분명히 해야 합니다. 즉, 프로그래밍 언어의 함수 호출은 본질적으로 스택 호출이라는 것입니다.

이 문장을 어떻게 이해하시나요? 코드를 실행할 때 함수를 만나면 항상 이 함수를 먼저 입력합니다. 이 함수에서 코드를 실행한 후 원래 코드 실행 라인으로 돌아가서 현재 함수를 호출하는 코드를 계속 실행합니다. 예를 들어, 다음 코드입니다.

function testA()
{
    echo 'A start.', PHP_EOL;
    testB();
    echo 'A end.', PHP_EOL;
}
function testB()
{
    echo 'B start.', PHP_EOL;
    echo 'B end.', PHP_EOL;
}
echo 'P start.', PHP_EOL;
testA();
echo 'P end.', PHP_EOL;

// P start.
// A start.
// B start.
// B end.
// A end.
// P end.

현재 페이지 P는 testA() 함수로 실행되면 testA() 함수에 들어가 내부 코드, 즉 P -> 그런 다음 testA() 함수는 testB() 함수를 호출하고 이제 testB()에 들어가서 P -> A -> testB()의 코드가 완료되면 testA()로 돌아가서 testA() 함수 본문의 내용을 계속 실행하고, 마지막으로 페이지 P로 돌아가서 아래쪽으로 계속 실행합니다. 즉, B -> A ->; 피.

위의 설명이 이해가 안 되신다면, 몇 번 더 읽어보시고 주의 깊게 공부해 보시기 바랍니다. 이것은 단지 스택 호출 프로세스가 아닌가? !

이런 식으로 보면, 프로그래밍 언어에서 스택은 정말 뼈 속에 깊이 박혀있습니다. 코드를 개발하는 동안에는 스택을 사용해야 하기 때문입니다. "재귀"는 스택의 보다 일반적인 구현입니다.

function recursion($n)
{
    if ($n == 0 || $n == 1) {
        return 1;
    }
    $result = recursion($n - 1) * $n;
    return $result;
}

echo recursion(10), PHP_EOL;

이것은 계승 알고리즘의 간단한 재귀 구현이므로, 우리 코드가 가장 먼저 계산하는 것은 스택 맨 아래의 n이 1이라는 것입니다. 스택을 팝한 후 1을 반환합니다. 다시 팝합니다. 1에 2를 곱한 다음 1에서 10까지의 계승 결과가 계산될 때까지 2에 3을 곱하여 스택을 계속해서 팝합니다.

저희 면접에서도 재귀와 관련된 면접 질문이 많이 나오므로 재귀가 실제로는 스택의 한 형태라는 점을 파악한 다음 스택의 개념을 활용하여 전체 재귀 호출 프로세스를 분해해야 합니다. .

Queue Application

마지막으로 큐의 실용적인 응용 프로그램에 대해 이야기해 보겠습니다. 실제로 코드 수준에서 대기열의 좋은 예는 많지 않습니다. 더 일반적인 예로는 두 개의 대기열이 병합되고 대기열에서 제거되거나(댄스 파트너 문제) 두 개의 대기열이 함께 대기열에서 제거되고 두 개의 대기열이 이전에 한쪽에서 대기열에서 제거되는 경우가 있습니다. 이런 종류의 문제는 다른 하나의 대기열에서 제외될 수 있습니다. 관련 주제를 직접 찾아보실 수 있습니다. 상대적으로 보면 면접질문 중 큐알고리즘 질문은 상대적으로 드물며, 대학원 입시를 포함해 대부분 선발판단 질문 형태로 나타난다. 그러나 실제 응용 프로그램에서 대기열은 이제 높은 동시성 문제를 해결하기 위한 슈퍼 마법의 무기이며 면접관이 귀하의 경험을 판단하는 중요한 요소이기도 합니다.

실제 프로젝트 개발에서 큐의 가장 일반적인 기능 중 하나는 플래시 킬 문제입니다. 기차표를 움켜쥐거나 샤오미 휴대폰을 훔치는 것처럼, 정시가 되면 엄청난 양의 요청이 쏟아진다. 이를 서버에만 의존해서 처리한다면 초고동시성은 서버에 큰 부담을 줄 뿐만 아니라 과매도, 거래 예외 등과 같은 높은 동시성 시나리오에서만 발생하는 다양한 문제가 발생할 수도 있습니다. (여러 스레드가 동시에 데이터를 업데이트합니다)

而队列，正是解决这个问题的一把好手。通常我们会使用的队列系统（redis、rabbitmq）都是以内存为主的队列系统，它们的特点就是存储非常快。由前端（生产者）生成的大量请求都存入队列中（入队），然后在后台脚本（消费者）中进行处理（出队）。前端只需要返回一个正在处理中，或者正在排队的提示即可，然后后台处理完成后，通知前台显示结果。这样，在一个秒杀场景中基本上就算是解决了高并发的问题了。当然，现实环境可能还需要考虑更多因素，但核心都是以队列的方式来解决这种瞬间高并发的业务功能。

另外，队列还有一个重要的业务场景，那就是通知、消息、邮件、短信之类的这种信息发送。因为队列的所能解决的一些问题的最大特点就是需要生产者/消费者的业务解耦。通常我们在群发消息时都会批量进行大规模的发送，这时就只需要准备好消息内容和对应的手机号、设备id，就可以让系统在后台队列中慢慢进行消息发送了，而不需要我们的前端一直等待消息全部发送完成。

这时，不少小伙伴又看出了一点点门道了。队列这货在实际应用中，就是多线程的感觉呀，JS 中的事件回调，CPU 的碎片时间轮询可不就是一种队列的真实应用嘛。还有设计模式中的“观察者模式”，本身就是事件回调这种机制的一种编程范式，所以，用它来实现的很多功能中，我们都能看到队列的影子。

总结

看看，一个栈，一个队列，竟然都是我们在开发过程中天天要接触的东西。是不是感觉自己的脑容量不够用了？仔细再想想，还有哪些东西和我们的栈、队列有关呢？其实只要把握住它们的两个本质就可以了：栈是后进先出（LIFO）或者说是先进后出（FILO），而队列是先进先出（FIFO）。

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.栈和队列/source/3.3栈和队列的应用.php

推荐学习：php视频教程

위 내용은 스택 및 큐 사용에 대한 올바른 자세(예제 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!