Очередь на основе фактической структуры данных PHP

задняя часть PHP внешний интерфейс алгоритм

что такое очередь

Очередь — это еще одна линейная структура данных, которая следует принципу FIFO. Есть два конца очереди для работы, один конец удаляется из очереди, а другой конец ставится в очередь. Эта особенность отличается от стека, который имеет только один конец, который можно использовать для операций. Постановка в очередь всегда в конце, а удаление из очереди всегда впереди.

Общие операции

  • поставить в очередь -> поставить в очередь
  • исключить из очереди -> исключить из очереди
  • peek -> возвращает передний элемент очереди
  • isEmpty -> пусто

PHP-реализация

Сначала мы определяем QueueInterface.

interface QueueInterface
{
    public function enqueue(string $item);
    public function dequeue();
    public function isEmpty();
    public function peek();
}

Давайте посмотрим на реализацию очереди на основе массива.

class ArrQueue implements QueueInterface
{
    private $queue;
    private $limit;

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

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

    public function dequeue()
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('queue is empty');
        } else {
            array_shift($this->queue);
        }
    }

    public function enqueue(string $item)
    {
        if (count($this->queue) >= $this->limit) {
            throw new \OverflowException('queue is full');
        } else {
            array_unshift($this->queue, $item);
        }
    }

    public function peek()
    {
        return current($this->queue);
    }
}

Благодаря мощной структуре массивов PHP мы можем легко написать основной метод работы с очередью. Конечно же, лучший в мире язык оправдывает свою репутацию.

Возможно, остроумные одноклассники догадались, что я уже определил интерфейс очереди, и реализация очереди должна быть больше, чем приведенная выше. Давайте посмотрим на реализацию на основе связанного списка.

class LinkedListQueue implements QueueInterface
{
    private $limit;
    private $queue;

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

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

    public function peek()
    {
        return $this->queue->getNthNode(0)->data;
    }

    public function enqueue(string $item)
    {
        if ($this->queue->getSize() < $this->limit) {
            $this->queue->insert($item);
        } else {
            throw new \OverflowException('queue is full');
        }
    }

    public function dequeue()
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('queue is empty');
        } else {
            $lastItem = $this->peek();
            $this->queue->deleteFirst();

            return $lastItem;
        }
    }
}

Он включает в себя предыдущую реализацию связанного списка, студенты, которые не знают деталей, могут перейти кздесьпосмотри.

Очередь в Спл

Мощный PHP имеет встроенную реализацию очереди, и методы, которые можно использовать, аналогичны тем, которые мы реализовали сами выше.

class SqlQueue
{
    private $splQueue;

    public function __construct()
    {
        $this->splQueue = new \SplQueue();
    }

    public function enqueue(string $data = null)
    {
        $this->splQueue->enqueue($data);
    }

    public function dequeue()
    {
        return $this->splQueue->dequeue();
    }
}

приоритетная очередь

Очередь с приоритетом — это особый вид очереди, и порядок постановки в очередь или исключения из очереди зависит от веса каждого узла.

последовательная последовательность

Очереди с приоритетом можно разделить на очереди с упорядоченным приоритетом и очереди с неупорядоченным приоритетом. Существует два типа очередей с упорядоченным приоритетом: обратный порядок или последовательный порядок. В последовательной последовательности мы можем быстро найти узел с наибольшим или наименьшим приоритетом, а сложность — O(1). Но его вставка займет больше времени, потому что мы должны проверить приоритет каждого узла и вставить его в соответствующую позицию.

неупорядоченная последовательность

В неупорядоченной последовательности при вставке новых узлов нам не нужно определять позицию по их приоритету. При входе в очередь он вставляется в конец очереди, как обычная очередь. Но когда мы хотим удалить элемент с наивысшим приоритетом, мы должны сканировать каждый узел, чтобы определить, какой из них имеет наивысший приоритет для удаления. Далее мы реализуем очередь с последовательным приоритетом на основе связанного списка.

class LinkedListPriorityQueue
{
    private $limit;
    private $queue;


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

    public function enqueue(string $data = null, int $priority)
    {
        if ($this->queue->getSize() > $this->limit) {
            throw new \OverflowException('Queue is full');
        } else {
            $this->queue->insert($data, $priority);
        }
    }

    public function dequeue(): string
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('Queue is empty');
        } else {
            $item = $this->peek();
            $this->queue->deleteFirst();

            return $item->data;
        }
    }

    public function peek()
    {
        return $this->queue->getNthNode(0);
    }

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

круговая очередь

Чтобы в полной мере использовать векторное пространство, метод преодоления явления «ложного переполнения» состоит в том, чтобы представить векторное пространство как сквозное кольцо и назвать этот вектор круговым вектором. Хранящаяся в нем очередь называется циклической очередью. Циклическая очередь тоже является массивом, но логически соединяет голову и хвост массива, образуя циклическую очередь.Когда хвост массива заполнен, необходимо оценить, пуста ли голова массива, и продолжить для хранения данных, если он не пуст.

class CircularQueue implements QueueInterface
{
    private $queue;
    private $limit;
    private $front = 0;
    private $rear = 0;

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

    public function isEmpty()
    {
        return $this->front === $this->rear;
    }

    public function isFull()
    {
        $diff = $this->rear - $this->front;

        if ($diff == -1 || $diff == ($this->limit - 1)) {
            return true;
        }

        return false;
    }

    public function peek()
    {
        return $this->queue[$this->front];
    }

    public function dequeue()
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('Queue is empty');
        }

        $item = $this->queue[$this->front];
        $this->queue[$this->front] = null;
        $this->front = ($this->front + 1) % $this->limit;

        return $item;
    }

    public function enqueue(string $item)
    {
        if ($this->isFull()) {
            throw new \OverflowException('Queue is full');
        }

        $this->queue[$this->rear] = $item;
        $this->rear = ($this->rear + 1) % $this->limit;

    }
}

дека

Все очереди, которые мы реализовали до сих пор, помещаются в конец очереди и выходят из нее в начале очереди. В особых случаях мы надеемся, что как голова, так и хвост команды могут войти в очередь или выйти из нее.Такая структура называется двусторонней очередью. Основываясь на структуре связанного списка, которую мы реализовали ранее, мы можем легко реализовать такую ​​структуру.

class LinkedListDeQueue
{
    private $limit = 0;
    private $queue;

    public function __construct(int $limit = 0)
    {
        $this->limit = $limit;
        $this->queue = new \DataStructure\LinkedList\LinkedList();
    }

    public function dequeueFromFront(): string 
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('Queue is empty');
        }

        $item = $this->queue->getNthNode(0);
        $this->queue->deleteFirst();

        return $item->data;
    }

    public function dequeueFromBack(): string 
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('Queue is empty');
        }

        $item = $this->queue->getNthNode($this->queue->getSize() - 1);
        $this->queue->deleteLast();

        return $item->data;
    }

    public function isFull()
    {
        return $this->queue->getSize() >= $this->limit;
    }

    public function enqueueAtBack(string $data = null)
    {
        if ($this->isFull()) {
            throw new \OverflowException('queue is full');
        }

        $this->queue->insert($data);
    }

    public function enqueueAtFront(string $data = null)
    {
        if ($this->isFull()) {
            throw new \OverflowException('queue is full');
        }

        $this->queue->insertAtFirst($data);
    }

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

    public function peekFront()
    {
        return $this->queue->getNthNode(0)->data;
    }

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

Он включает в себя предыдущую реализацию связанного списка, студенты, которые не знают деталей, могут перейти кздесьпосмотри.

Суммировать

Стеки и очереди — наши наиболее часто используемые структуры данных, и мы увидим применение этих двух абстрактных типов данных в других сложных структурах данных. В следующей главе мы перейдем к рекурсии структур данных PHP — распространенному способу упрощения сложных задач.

Тематическая серия

Адрес каталога серии тем по базовой структуре данных PHP:github.com/...Он в основном использует синтаксис PHP для обобщения основных структур данных и алгоритмов. Есть также базовые знания, которые легко игнорировать в нашей повседневной разработке PHP, и некоторые практические предложения по спецификации, развертыванию и оптимизации в современной разработке PHP, а также углубленное исследование характеристик языка Javascript.

Категории