乐趣区

关于php:PHP数据结构栈和队列的应用

jiezi

通过栈和队列的学习，咱们仿佛会感觉到其实数据结构还是非常简单的嘛。当然，这只是一个开始，咱们从程序表、链表开始，到当初的栈和队列，其实都是为了未来在铺路。在树和图的遍历算法中，都能够见到栈和队列的身影。在这里，咱们先简略的看看栈和队列的一些理论利用。

回文题

假如有一段文字，咱们要判断它是不是“回文”（不是回族兄弟的文字）。就能够利用栈来解决这个问题。

回文指的就是将这段文字一分为二之后，后面一段内容和前面一段内容是完全相同的，然而程序是相同的。比方十分闻名的：上海自来水来自海上。上海自来，来自海上，这样的两段构造在一句话里就形成了一段回文。又比方单数长度的一段字符：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() 来进行的程序栈的操作而已。惟一须要留神的就是对于字符长度奇偶数的不同，咱们要取的中位数也相应的要产生扭转。

回文算法还是比较简单的，另外还常常会呈现的像是简略的括号匹配、算式运算、中断转后缀表达式这类的题目都是栈的典型算法面试题。大家能够自行查找相干的内容来尝试尝试。

递归

在讲递归前，咱们要弄清楚一件事件，那就是：编程语言中的函数调用实质上就是栈的调用。

怎么了解这句话呢？当咱们执行代码时，如果遇到一个函数，总是会先进入到这个函数中，运行完这个函数中的代码之后才会再回到原来的代码执行线中继续执行调用以后这个函数的代码。比方上面这段代码。

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 -> A。而后 testA() 函数又调用了 testB() 函数，那么当初就进入了 testB() 中并执行该函数体内的代码，也就是 P -> A -> B。当 testB() 的代码运行实现后，返回到 testA() 继续执行 testA() 函数体外面的内容，最初回到页面 P 持续向下执行，也就是 B -> A -> P。

下面这段形容如果一次没看明确的话，请再多看几次，细细品。这不就是一个栈的调用过程嘛！！

这么一看，在编程语言中，栈还真是深入骨髓般的存在。因为你只有是在开发代码，那么你肯定就是在使用栈这个货色了。而“递归”，则是栈的更典型的实现。

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，再持续出栈就是 2 乘以 3，顺次类推，直到计算出从 1 到 10 的阶乘后果。

递归相干的面试题也是咱们在面试中十分常见的内容，所以咱们肯定要把握好递归其实就是栈的一种表现形式，而后使用栈的思维来解构整个递归的调用过程。

队列利用

最初，咱们再讲讲队列的一些理论利用。队列在代码层面其实并没有太多很好的示例，比拟常见的可能有两个队列合并出队（舞伴问题）或者两组队列一起出队，一边出两个另一个能力出一个之类的这种问题。大家能够自行查找一下相干的题目。相对来说，队列的算法题在面试题中还是比拟少的，包含在考研的时候也多是以抉择判断之类的题目呈现的。不过，在理论利用中，队列当初却是解决高并发问题的超级法宝，也是面试官判断你教训的一个重要内容。

在理论的我的项目开发中，队列最典型的一个性能就是秒杀问题。就像抢火车票或者抢小米手机一样，在整点的时候，大量的申请涌入，如果仅仅依附服务器来解决，超高的并发量不仅会带给服务器微小压力，而且还有可能呈现各种高并发场景下才会呈现的问题，比方超卖、事务异样等。（多个线程同时更新数据）

而队列，正是解决这个问题的一把好手。通常咱们会应用的队列零碎（redis、rabbitmq）都是以内存为主的队列零碎，它们的特点就是存储十分快。由前端（生产者）生成的大量申请都存入队列中（入队），而后在后盾脚本（消费者）中进行解决（出队）。前端只须要返回一个正在解决中，或者正在排队的提醒即可，而后后盾解决实现后，告诉前台显示后果。这样，在一个秒杀场景中基本上就算是解决了高并发的问题了。当然，事实环境可能还须要思考更多因素，但外围都是以队列的形式来解决这种霎时高并发的业务性能。

另外，队列还有一个重要的业务场景，那就是告诉、音讯、邮件、短信之类的这种信息发送。因为队列的所能解决的一些问题的最大特点就是须要生产者 / 消费者的业务解耦。通常咱们在群发音讯时都会批量进行大规模的发送，这时就只须要筹备好消息内容和对应的手机号、设施 id，就能够让零碎在后盾队列中缓缓进行音讯发送了，而不须要咱们的前端始终期待音讯全副发送实现。

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

总结

看看，一个栈，一个队列，居然都是咱们在开发过程中天天要接触的货色。是不是感觉本人的脑容量不够用了？认真再想想，还有哪些货色和咱们的栈、队列无关呢？其实只有把握住它们的两个实质就能够了：栈是后进先出（LIFO）或者说是先进后出（FILO），而队列是先进先出（FIFO）。

测试代码：

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

参考资料：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020 版，天勤考研

各自媒体平台均可搜寻【硬核项目经理】

退出移动版