PHP data structure basic stack-PHP Tutorial-php.cn

PHP data structure basic stack

不言

Release： 2023-04-02 18:14:02

Original

1465 people have browsed it

This article mainly introduces the basic stack of PHP data structure, which has certain reference value. Now I share it with everyone. Friends in need can refer to it

Stack and Queue

Stacks and queues are linear structures like the doubly linked list, the basis of actual PHP data structure mentioned before.

What are the characteristics of the stack

The stack follows the last-in-first-out principle (LIFO). This means that the stack has only one outlet for pushing elements and popping elements. When we perform push or pop operations, we must pay attention to whether the stack is full or whether the stack is empty.

Common operations

Without further ado, let’s look directly at the common operations we perform on the stack.

push
pop
##top
isEmpty
...

PHP implementation

First we define a StackInterface.

interface StackInterface
{
    public function push(string $item);
    public function pop();
    public function top();
    public function isEmpty();
}

Copy after login

Let’s look at the stack implementation based on arrays

class ArrStack implements StackInterface
{
    private $stack;
    private $limit;

    public function __construct(int $limit = 20)
    {
        $this->limit = $limit;
        $this->stack = [];
    }

    public function __get($val)
    {
        return $this->$val;
    }

    public function push(string $data = null)
    {
        if (count($this->stack) < $this->limit) {
            array_push($this->stack, $data);
        } else {
            throw new \OverflowException(&#39;stack is overflow&#39;);
        }
    }

    public function pop()
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException(&#39;stack is empty&#39;);
        } else {
            return array_pop($this->stack);
        }
    }

    public function isEmpty()
    {
        return empty($this->stack);
    }

    public function top()
    {
        return end($this->stack);
    }

Copy after login

Thanks to PHP’s powerful array structure, we can easily write out the basic operation methods of the stack. Sure enough, the best language in the world lives up to its reputation.

Some students said that the stack and the previous linked list are both linear structures. Can we directly use the linked list to implement the stack? This question is very sharp, and the answer is yes.

Maybe smart classmates have guessed that I have defined a stack interface before, and the implementation of the stack must be more than just the above one. Let’s look at the implementation based on linked lists.

class LinkedListStack implements StackInterface
{
    private $stack;
    private $limit;

    public function __construct(int $limit)
    {
        $this->limit = $limit;
        $this->stack = new LinkedList();
    }

    public function top()
    {
        return $this->stack->getNthNode($this->stack->getSize() - 1)->data;
    }

    public function isEmpty()
    {
        return $this->stack->getSize() === 0;
    }

    public function pop()
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException(&#39;stack is empty&#39;);
        } else {
            $lastItem = $this->top();
            $this->stack->deleteLast();

            return $lastItem;
        }
    }

    public function push(string $item)
    {
        if ($this->stack->getSize() < $this->limit) {
            $this->stack->insert($item);
        } else {
            throw new \OverflowException(&#39;stack is overflow&#39;);
        }
    }

Copy after login

It involves the previous linked list implementation. Students who don’t understand the details can go here to take a look. Some students asked again, what is the use of that stack? This is a very good question. Let’s look at a requirement.

Please implement a mathematical expression checking class, enter the following expression, and the expected result is true.

"8 * (9 -2) + { (4 * 5) / ( 2 * 2) }

Copy after login

The following is false.

"5 * 8 * 9 / ( 3 * 2 ) )"

Copy after login

The following is also false.

"[{ (2 * 7) + ( 15 - 3) ]"

Copy after login

Think about it for yourself, and then look at the implementation.

class ExpressionChecker
{
    //$expressions[] = "8 * (9 -2) + { (4 * 5) / ( 2 * 2) }";
    //$expressions[] = "5 * 8 * 9 / ( 3 * 2 ) )";
    //$expressions[] = "[{ (2 * 7) + ( 15 - 3) ]";

    public function check(string $expression): bool
    {
        $stack = new \SplStack();

        foreach (str_split($expression) as $item) {
            switch ($item) {
                case '{':
                case '[':
                case '(':
                    $stack->push($item);
                    break;

                case '}':
                case ']':
                case ')':
                    if ($stack->isEmpty()) return false;

                    $last = $stack->pop();

                    if (
                        $item == '{' && $last != '}' ||
                        $item == '(' && $last != ')' ||
                        $item == '[' && $last != ']'
                    )
                        return false;

                    break;
            }
        }

        if ($stack->isEmpty()) {
            return true;
        }

        return false;
    }
}

Copy after login

Special series

PHP basic data structure special series directory address: https://github.com/... Mainly uses PHP syntax to summarize basic data structures and algorithms. There are also basic knowledge that is easily overlooked in our daily PHP development and some practical suggestions on standardization, deployment, and optimization in modern PHP development. There is also an in-depth study of the characteristics of the Javascript language.

The above is the entire content of this article. I hope it will be helpful to everyone's study. For more related content, please pay attention to the PHP Chinese website!

Related recommendations:

php redis locking and unlocking

PHP method of operating Beanstalkd and parameter comments

The above is the detailed content of PHP data structure basic stack. For more information, please follow other related articles on the PHP Chinese website!