PHP 데이터 구조 기본 스택-PHP 튜토리얼-php.cn

PHP 데이터 구조 기본 스택

不言

풀어 주다： 2023-04-02 18:14:02

원래의

1505명이 탐색했습니다.

이 글은 주로 PHP 데이터 구조의 기본 스택을 소개하며, 이는 특정 참조 가치가 있습니다. 이제는 필요한 친구들이 참조할 수 있습니다.

Stack 및 Queue#🎜🎜 #

스택과 큐는 앞에서 언급한 실제 PHP 데이터 구조의 기초인 이중 연결 목록과 같은 선형 구조입니다.

스택의 특징은 무엇인가요

스택은 후입선출(LIFO) 원칙을 따릅니다. 즉, 스택에는 요소를 푸시하고 요소를 팝하는 데 필요한 콘센트가 하나만 있습니다. 푸시 또는 팝 작업을 수행할 때 스택이 가득 찼는지 아니면 비어 있는지 주의해야 합니다.

일반 작업

더 이상 고민하지 않고 스택에서 수행하는 일반적인 작업을 직접 살펴보겠습니다.

push
pop
상단
isEmpty
...

먼저 StackInterface를 정의합니다.

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

로그인 후 복사

배열 기반 스택 구현을 살펴보겠습니다

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

로그인 후 복사

PHP의 강력한 배열 구조 덕분에 스택의 기본 작업 방법을 쉽게 작성할 수 있습니다. 물론, 세계 최고의 언어는 그 명성에 걸맞게 살아갑니다.

그런데 한 학우가 말하기를, 스택과 이전 연결 리스트가 모두 선형 구조라고 하더군요. 연결 리스트를 직접 사용하여 스택을 구현할 수 있나요? 이 질문은 매우 예리하며 대답은 '예'입니다.

아마도 똑똑한 학생들은 내가 이전에 스택 인터페이스를 정의한 적이 있고 스택의 구현은 위의 것 이상일 것이라고 추측했을 것입니다. 연결리스트 기반의 구현을 살펴보겠습니다.

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

로그인 후 복사

이전의 연결리스트 구현이 포함되어 있습니다. 자세한 내용을 이해하지 못하는 학생은 여기로 가서 살펴보세요. 일부 학생들은 다시 묻습니다. 그 스택의 용도는 무엇입니까? 이것은 매우 좋은 질문입니다. 요구사항을 살펴보겠습니다.

수학 수식 검사 클래스를 구현하고, 다음 수식을 입력하면 예상한 결과가 true가 됩니다.

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

로그인 후 복사

다음 내용은 거짓입니다.

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

로그인 후 복사

다음 내용도 거짓입니다.

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

로그인 후 복사

스스로 생각해보고 구현을 살펴보세요.

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

로그인 후 복사

특수 시리즈