Correct posture for using stacks and queues (with examples)

Through the study of stacks and queues, we seem to feel that the data structure is actually very simple. Of course, this is just the beginning. We started from sequence lists and linked lists to the current stacks and queues, which are actually paving the way for the future. Stacks and queues can be seen in tree and graph traversal algorithms. Here, we first briefly look at some practical applications of stacks and queues.

Palindrome Question

Suppose there is a text, we need to determine whether it is a "palindrome" (not the text of the Hui brothers). You can use the stack to solve this problem.

A palindrome means that after dividing this paragraph of text into two, the content of the previous paragraph and the content of the following paragraph are exactly the same, but the order is reversed. For example, it is very famous: Shanghai’s tap water comes from the sea. Shanghai comes from the sea. This two-part structure forms a palindrome in one sentence. Another example is a character of even length: abcddcba, which is also a palindrome.

Similar questions are actually easy to appear in some simple algorithm interview questions. I believe many friends have already seen the clues. We can push the first half of the paragraph into the stack, and then pop it out one by one. By comparing the stack with the second half, you can determine whether the current string is a palindrome. Don’t just talk without practicing, let’s implement the code.

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

It's very simple, just use array_push() and array_pop() to perform sequential stack operations. The only thing that needs to be noted is that for different odd and even character lengths, the median we want to take will also change accordingly.

The palindrome algorithm is relatively simple. In addition, questions such as simple bracket matching, arithmetic operations, and infix-to-suffix expressions often appear, which are typical stack algorithm interview questions. You can search for relevant content and try it yourself.

Recursion

Before talking about recursion, we need to clarify one thing, that is: function calls in programming languages ​​are essentially stack calls.

How to understand this sentence? When we execute code, if we encounter a function, we will always enter this function first. After running the code in this function, we will return to the original code execution line to continue executing the code that calls the current function. For example, the following code.

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.

When the current page P runs to the testA() function, it enters the testA() function to execute its internal code, that is, P -> A . Then the testA() function calls the testB() function, and now it enters testB() and executes the code in the function body, which is P -> A -> B . When the code of testB() is completed, return to testA() to continue executing the content in the testA() function body, and finally return to page P to continue downward execution, that is, B -> A -> P .

If you don’t understand the description above, please read it a few more times and study it carefully. Isn't this just a stack calling process? !

#Looking at it this way, in programming languages, the stack is really deep in the bones. Because as long as you are developing code, you must be using the stack. "Recursion" is a more typical implementation of the stack.

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

echo recursion(10), PHP_EOL;

This is a simple recursive implementation of the factorial algorithm. Since recursion will create a stack, the first thing our code calculates is that n at the bottom of the stack is 1. After popping the stack and returning 1, When popping from the stack again, multiply 1 by 2, and when popping from the stack again, multiply by 2 by 3, and so on, until the factorial result from 1 to 10 is calculated.

Recursion-related interview questions are also very common in our interviews, so we must grasp that recursion is actually a form of stack, and then use the stack's Thinking to deconstruct the entire recursive calling process.

Queue Application

Finally, let’s talk about some practical applications of queues. In fact, there are not many good examples of queues at the code level. The more common ones may be that two queues are merged and dequeued (dance partner problem) or two queues are dequeued together, and two queues are dequeued on one side before one can be dequeued by the other. This kind of problem. You can search for related topics by yourself. Relatively speaking, queue algorithm questions are relatively rare among interview questions, and most of them appear in the form of selection judgment questions, including in postgraduate entrance examinations. However, in practical applications, queues are now a super magic weapon to solve high concurrency problems, and they are also an important part of the interviewer's judgment of your experience.

In actual project development, one of the most typical functions of the queue is the flash sale problem. Just like grabbing train tickets or Xiaomi mobile phones, at the top of the hour, a large number of requests pour in. If you only rely on the server to handle it, the ultra-high concurrency will not only put huge pressure on the server, but also may cause various problems. Problems that only occur in high concurrency scenarios, such as oversold, transaction exceptions, etc. (Multiple threads update data at the same time)

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

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

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

总结

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

测试代码：

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

推荐学习：php视频教程

The above is the detailed content of Correct posture for using stacks and queues (with examples). For more information, please follow other related articles on the PHP Chinese website!