For the logical structure, we also start with the simplest. Stack, queue, these two words are familiar to most people, but the heap and the stack are actually two things. Don’t let the interviewer confuse you during the interview. A heap is a tree structure, or a complete binary tree structure. Today, we’re going to focus on the application of this stack.

What is a stack?

A stack is generally a sequential data structure. Its biggest feature is last in, first out (LIFO), or conversely first in, first out (FILO). What exactly do these two sentences mean? The best example of this is something that you absolutely see when you watch a TV show, especially a shootout: the magazine.

Cartridges are loaded one by one into the magazine, that is, the first bullet is placed at the bottom, while the shot is fired in reverse order from the top of the magazine, the first bullet is the last bullet to be fired.

This is actually a pretty good example, so let’s unify the terminology. The first bullet is at the bottom of the stack, this position is called the bottom of the stack, the last bullet is at the top of the stack, this position is called the top of the stack, the bullet is the top of the stack, this operation is called the “out of the stack.”

From the definition of the above terms, we can see that the logical operation of the stack is mainly “on” and “off”, and the logical structure needs to care about the “top” and “bottom” of the stack during the entry and exit of the stack. Of course, there is no problem with using a sequential or chained logical structure for the stack, so let’s look at each one.

Order of the stack

First, the implementation of the sequence stack is relatively simple. Since it’s a sequential structure, it’s an array. However, we also need to keep track of the “top” or “bottom” of the stack, so we encapsulate this array of the sequential stack in a class. Also, define a property in this class to indicate the current “top” or “bottom” pointer of the stack, which is where the current “top” or “bottom” pointer is in the array. In general, we only need to record the location of the “top of the stack” and default the “bottom of the stack” to -1. Because array subscripts themselves start at 0, when the “top of the stack” attribute is -1, the stack is empty because the “top” and “bottom” of the stack are together and have no elements.

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

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

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

Next is the “push” and “push” operation, first look at the code.

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

Stacking is as simple as adding content to the array element, and then $top++ will do the trick. However, if the C language, because it has a limit on the size of the array, so when the stack is loaded, we need to check whether the stack is full. Of course, in PHP we don’t have that concern.

Sequential stack to stack diagram

If the current stack is empty, it doesn’t make any difference to the language, because if it is smaller than -1, it will be a problem to use the stack again. If the stack is empty at the time of the exit, instead of giving $top–, get the top element and return it.

Sequential stack out diagram

Let’s look at the test results for 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)
//   }

Isn’t it easy to manipulate stacks through arrays? After reading and learning the chain stack, we will also talk about the array stack operation function that has been prepared for us by PHP, which will be more convenient to use.

Chain stack

In fact, for the chain storage structure, the core content is still the same, the same is to care about the top of the stack, but also to care about the operation in and out of the stack. However, in the chained case, we can achieve the “top of the stack” effect by making the inserted data stay at the top of the chain. This way, we don’t need a special property to hold the current top position of the stack. It’s much clearer to just look at a picture.

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

The structure of the data is a typical chain structure on it, mainly depends on how the operation in and out of the stack is carried out.

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

Initializing an empty stack in a chain stack makes little sense. We could just define a null variable and chain it, but here we’re sticking with the order stack. Just as the bottom of a sequential stack is -1, in a chain stack we also agree that the bottom of the stack is a NULL object node.

The next step is the push operation. So what we’re going to do is we’re going to use the header method, which is we’re going to put the new element at the top of the list. You instantiate a node and then point the next of that node to the head node of the linked list. Then make the current node the new head node for the list, as shown in the figure below.

In the same way, the stack operation is similar. It turns the head node into the next node of the current head node until the current node becomes null, which means the stack is empty, as shown in the figure:

Finally, let’s test the code for the chained stack as well.

$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

Many of you have already seen that we spent four articles talking about the importance of ordered lists and linked lists in linear structures. They really are the basis of all other logical structures. Not just stacks, but queues, trees, graphs, we all have linear and chained implementations of different structures. Of course, it is more important to understand the difference between them, because in different business scenarios, two different storage structures can really make a completely different experience.

PHP provides us with array stack operations

Finally, let’s take a brief look at the two array manipulation functions that are already available for us in PHP. With them, our operations can be simplified to a very idiotic level for the order stack.

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

I think a lot of you have already used these two functions. Array_push () is just a function of pushing a piece of data into an array, or simply adding a piece of data to an array. Array_pop (), on the other hand, pops the data from the last position in the array. Is it exactly the same concept as the sequential stack we implemented above? Yes, now that the locale is ready for us, it’s easy to use these two functions directly to implement stack operations in PHP in most cases, except when chaining is required.

conclusion

The logical structure of the stack is not very simple and clear ah, in daily application in fact, the use of the stack is very extensive. For example, prefix arithmetic, infix arithmetic and suffix arithmetic are transformed. For example, we should contact BFS (deep search) when learning trees and graphs, and then lead to the concept of recursion according to BFS. In addition, in the parsing of the character of some symmetric matching, palindrome algorithm judgment, and so on, these are the typical applications of the stack. The stack, so to speak, holds up half of the computer algorithm. And what about the other half? Which is, of course, what we’re going to talk about next time: queues.

Test code:

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3. Stack and Queue /source/3.1 Stack related logical operations. PHP

References:

Data Structures, 2nd Ed., Weimin Yan

Data Structure, 2nd Edition, Yue Chen

“Notes on Data Structure with High Score”, 2020 edition, Tianqin postgraduate entrance examination

Search for “Hardcore Project Manager” on all media platforms