Структура данных PHP

Структура данных, или абстрактный тип данных (ADT) представляет собой модель, которая определяет набор операций. Большинство из нас знакомы с Stacks и Queues. На этой странице Я представлю Вам два основных абстрактных типа данных: Stacks и Queues.

Stacks (стек)

Stack (стек) — это куча объектов, например: стопка книг на столе. В компьютерных определениях, стек представляет собой последовательный набор с определенным свойством, первый объект перемещается если последний объект добавить в стек. Это свойство обычно называют last in, first out , или LIFO . Автоматы с конфетами, сигаретами работают по тому же принципу; последний элемент помещённый в стеллаж, выдаётся в первую очередь.

В абстрактных терминах, стек — это линейный список, в котором все элементы дополнения “push” и перемещения “pop”, список ограниченный в один конец — определяется в стеке как “top”. Основные операции, которые определяет стек:

  • init — создание стека.
  • push — добавит элемент в вершине стека.
  • pop — извлечь последний элемент, добавленный в вершине стека.
  • top — посмотрите на элемент в вершине стека, не удаляя его.
  • isEmpty — возвращать ли стек не содержащий несколько элементов.

Если стек заполнен, и уже не осталось слотов, это переполнение — от этого фраза “переполнение стека”.

Зная, что наш стек определяется по методу LIFO , в частности, push и pop, его можно легко реализовать используя массивы массивы, готовыми операциями push и pop.

Простой стек выглядит так:



<?php
class ReadingList
{
    protected $stack;
    protected $limit;

    public function __construct($limit = 10) {
        // initialize the stack
        $this->stack = array();
        // stack can only contain this many items
        $this->limit = $limit;
    }

    public function push($item) {
        // trap for stack overflow
        if (count($this->stack) < $this->limit) {
            // prepend item to the start of the array
            array_unshift($this->stack, $item);
        } else {
            throw new RunTimeException('Stack is full!');
        }
    }

    public function pop() {
        if ($this->isEmpty()) {
            // trap for stack underflow
	      throw new RunTimeException('Stack is empty!');
	  } else {
            // pop item from the start of the array
            return array_shift($this->stack);
        }
    }

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

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


В этом примере я использовал array_unshift() и array_shift() , а не array_push() и array_pop() так , что первый элемент стека всегда вершина. Вы могли бы использовать array_push() и array_pop() для поддержания семантической согласованности, в случае чего, N-й элемент стека станет верхним. Разницы нет, так или иначе, поскольку весь смысл абстрактного типа данных является абстрактными манипуляциями данными от реального применения.

Добавим некоторые элементы стека:



<?php
$myBooks = new ReadingList();

$myBooks->push('A Dream of Spring');
$myBooks->push('The Winds of Winter');
$myBooks->push('A Dance with Dragons');
$myBooks->push('A Feast for Crows');
$myBooks->push('A Storm of Swords');
$myBooks->push('A Clash of Kings');
$myBooks->push('A Game of Thrones');


Удаление некоторых элементов из стека:



<?php echo $myBooks->pop(); // outputs 'A Game of Thrones'
echo $myBooks->pop(); // outputs 'A Clash of Kings'
echo $myBooks->pop(); // outputs 'A Storm of Swords'


Смотрим что на вершине стека:



<?php
echo $myBooks->top(); // outputs 'A Feast for Crows'


Что, если его удалить.



<?php
echo $myBooks->pop(); // outputs 'A Feast for Crows'


Добавить новый элемент.



<?php $myBooks->push('The Armageddon Rag');
echo $myBooks->pop(); // outputs 'The Armageddon Rag'


Вы можете увидеть как стек работает на last in, first out основе. Последний элемент добавленный в стек, перемещает первый. Если продолжить pop, пока стек пуст, вы получите stack underflow runtime exception.



PHP Fatal error:  Uncaught exception 'RuntimeException' with message 'Stack is empty!' in /home/ignatius/Data Structures/code/array_stack.php:33
Stack trace:
#0 /home/ignatius/Data Structures/code/example.php(31): ReadingList->pop()
#1 /home/ignatius/Data Structures/code/array_stack.php(54): include('/home/ignatius/...')
#2 {main}
  thrown in /home/ignatius/Data Structures/code/array_stack.php on line 33


В SPLStack

SPL-расширение предоставляет набор структур стандартных данных, в том числе SplStack class (PHP5 >= 5.3.0). Мы можем реализовывать один и тот же объект, хотя и гораздо более лаконично, с помощью SplStack следующим образом:



<?php
class ReadingList extends SplStack
{
}


В классе SplStack реализуется на несколько больше методов, чем в первоначальном определении. Это происходит потому, что SplStack реализуется как двойная запись, который обеспечивает потенциал для осуществления прохода стека.

Двойная запись, которая является абстрактным типом данных, сама по себе является линейным набором объектов (узлов), используемых для представления определенной последовательности, где каждый узел в сборе содержит указатель на следующий узел в сборе. В своей простейшей форме в виде связанного списка выглядит так:

Структура данных: Stacks и Queues В двойной записи, каждый узел имеет два указателя, каждая из которых указывает на предыдущий и следующий узел в наборе. Этот тип структуры данных позволяет проход в обоих направлениях.

Структура данных для PHP программистов Stacks и Queues

Узлы, отмеченные крестиком (X) обозначают нулевой или вспомогательный — узел, который обозначает конец обхода пути (т.е. path terminator).

Поскольку ReadingList реализован как SplStack можно пройти в стек впереди top-down (сверху вниз) и в обратном направлении bottom-up (снизу вверх). По умолчанию режим для обхода SplStack — LIFO:



<?php
// top-down traversal
// default traversal mode is SplDoublyLinkedList::IT_MODE_LIFO|SplDoublyLinkedList::IT_MODE_KEEP
foreach ($myBooks as $book) {
    echo $book . "\n"; // prints last item first!
}


Для прохода в стек в обратном порядке, мы просто набираем iterator режиме FIFO (first in, first out):



<?php
// bottom-up traversal
$myBooks->setIteratorMode(
    SplDoublyLinkedList::IT_MODE_FIFO|SplDoublyLinkedList::IT_MODE_KEEP
);
foreach ($myBooks as $book) {
    echo $book . "\n";  // prints first added item first
}


Queues (очереди)

Если вы когда-нибудь были в очереди супермаркета, значить вы знаете, что первый человек в очереди стал в очередь раньше. В компьютерной терминологии очередь, является абстрактным типом данных, и работает на основе first in first out , или FIFO . Инвентаризации также осуществляется методом FIFO .

Основные операции, которые определяет Queues (очередь):

  • init — создать очередь.
  • enqueue — добавить элемент в конце очереди.
  • dequeue — удалить элемент в начале очереди.
  • isEmpty — возвращается очередь с элементами.

Поскольку SplQueue также реализован с использованием двойной записи, семантического значения top и pop сторнируются в этом контексте. Смотрим класс ReadingList queue:



<?php
class ReadingList extends SplQueue
{
}

$myBooks = new ReadingList();

// add some items to the queue
$myBooks->enqueue('A Game of Thrones');
$myBooks->enqueue('A Clash of Kings');
$myBooks->enqueue('A Storm of Swords');


SplDoublyLinkedList также реализует интерфейс ArrayAccess , можно также добавить элементы SplQueue и SplStack в качестве элементов массива:



<?php
$myBooks[] = 'A Feast of Crows';
$myBooks[] = 'A Dance with Dragons';


Удалить элементы из очереди:



<?php
echo $myBooks->dequeue() . "\n"; // outputs 'A Game of Thrones'
echo $myBooks->dequeue() . "\n"; // outputs 'A Clash of Kings' 


enqueue() — это псевдоним push() , но помните, что dequeue() — это не псевдоним pop() ; pop() с другими значением и функциями в контексте очереди. Если бы у нас был pop() , он бы удалил элемент в конце очереди, нарушая правила FIFO.

Аналогично, чтобы увидеть, начало очереди, мы должны использовать bottom() вместо top() :



<?php
echo $myBooks->bottom() . "\n"; // outputs 'A Storm of Swords'


Заключение

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

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

На следующей странице смотрите запись о другой структуре данных “ Структура данных: Trees

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML -теги и атрибуты: <a href= http://pixelcom.crimea.ua/"" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>