Структура данных, или абстрактный тип данных (ADT), представляет собой модель, которая определяется набором операций, которые могут быть выполнены над самим собой, и ограничена ограничениями воздействия этих операций. Это создает границу между тем, что можно сделать с базовыми данными, и тем, как это должно быть сделано.
Большинство из нас знакомы со стеками и очередями в обычном повседневном использовании, но какое отношение очереди супермаркетов и торговые автоматы имеют к структурам данных? Давай выясним. В этой статье я познакомлю вас с двумя основными абстрактными типами данных — стеком и очередью — которые берут свое начало в повседневном использовании.
Стеки
В обычном использовании стопка — это стопка объектов, которые обычно расположены слоями — например, стопка книг на вашем столе или стопка лотков в школьной столовой. На языке информатики, стек — это последовательный набор с определенным свойством, в котором последний объект, помещенный в стек, будет первым удаленным объектом. Это свойство обычно называют последним из первых , или LIFO . Автоматы по продаже конфет, чипсов и сигарет работают по тому же принципу; последний элемент, загруженный в стойку, распределяется первым.
Говоря абстрактно, стек — это линейный список элементов, в котором все добавления («толчок») и удаления из («поп») списка ограничены одним концом — определяется как «верх» (стека). ). Основные операции, которые определяют стек:
- init — создать стек
- push — добавить предмет на вершину стека.
- pop — удалить последний элемент, добавленный в верхнюю часть стека.
- top — посмотрите на элемент в верхней части стопки, не удаляя его.
- isEmpty — возвращает, если в стеке больше нет элементов.
Стек также может быть реализован, чтобы иметь максимальную емкость. Если стек заполнен и не содержит достаточно слотов для приема новых объектов, это называется переполнением — отсюда и фраза «переполнение стека». Аналогично, если операция pop выполняется в пустом стеке, возникает «переполнение стека».
Зная, что наш стек определяется свойством 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'
Вы можете видеть, что стек работает по принципу «первым пришел — первым вышел» Все, что добавлено в стек последним, удаляется первым. Если вы продолжите выталкивать элементы до тех пор, пока стек не станет пустым, вы получите исключение времени выполнения при переполнении стека.
Неустранимая ошибка PHP: необработанное исключение «RuntimeException» с сообщением «Стек пуст!» в / home / ignatius / структуры данных / code / array_stack.php: 33 Трассировки стека: # 0 / home / ignatius / Структуры данных / code / example.php (31): ReadingList-> pop () # 1 / home / ignatius / Структуры данных / code / array_stack.php (54): include ('/ home / ignatius / ...') # 2 {main} добавляется в / home / ignatius / структуры данных / code / array_stack.php в строке 33
О, привет … PHP любезно предоставил трассировку стека, показывающую стек вызовов выполнения программы до и до исключения!
SPLStack
Расширение SPL предоставляет набор стандартных структур данных, включая класс SplStack (PHP5> = 5.3.0). Мы можем реализовать тот же объект, хотя и гораздо более кратко, используя SplStack следующим образом:
<?php class ReadingList extends SplStack { }
Класс SplStack реализует несколько больше методов, чем мы изначально определили. Это связано с тем, что SplStack реализован в виде двусвязного списка, который обеспечивает возможность реализации проходного стека.
Связанный список, который сам является другим абстрактным типом данных, представляет собой линейную коллекцию объектов (узлов), используемых для представления определенной последовательности, где каждый узел в коллекции поддерживает указатель на следующий узел в коллекции. В простейшей форме связанный список выглядит примерно так:
В двусвязном списке каждый узел имеет два указателя, каждый из которых указывает на следующий и предыдущий узлы в коллекции. Этот тип структуры данных позволяет проходить в обоих направлениях.
Узлы, помеченные крестиком (X), обозначают нулевой или дозорный узел, который обозначает конец пути прохождения (т. Е. Терминатор пути).
Поскольку ReadingList реализован как SplStack , мы можем перемещаться по стеку вперед (сверху вниз) и назад (снизу вверх). Режим обхода по умолчанию для 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! }
Чтобы пройти по стеку в обратном порядке, мы просто устанавливаем режим итератора в FIFO (сначала во-первых, то, во-первых):
<?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 }
Очереди
Если вы когда-либо были в очереди на кассе супермаркета, то вы будете знать, что первый человек в очереди обслуживается первым. В компьютерной терминологии очередь — это другой абстрактный тип данных, который работает по принципу « первым пришел — первым обслужен», или FIFO . Управление запасами также осуществляется на основе FIFO, особенно если такие предметы имеют скоропортящийся характер.
Основные операции, которые определяют очередь:
- init — создать очередь
- enqueue — добавить элемент в «конец» (хвост) очереди.
- dequeue — удалить элемент из «фронта» (головы) очереди.
- isEmpty — возвращает, если в очереди больше нет элементов.
Поскольку SplQueue также реализован с использованием двусвязного списка, семантическое значение top и pop в этом контексте меняется на противоположное. Давайте переопределим наш класс ReadingList как очередь:
<?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.
Аналогично, чтобы увидеть, что находится впереди (в top() очереди, мы должны использовать bottom() вместо top() :
<?php echo $myBooks->bottom() . "n"; // outputs 'A Storm of Swords'
Резюме
В этой статье вы увидели, как в программировании используются абстрактные типы данных стека и очереди. Эти структуры данных являются абстрактными в том смысле, что они определяются операциями, которые могут выполняться над самим собой, создавая тем самым стену между его реализацией и базовыми данными.
Эти структуры также ограничены эффектом таких операций: вы можете добавлять или удалять элементы только из верхней части стека, а также удалять только элементы из передней части очереди или добавлять элементы из задней части очереди.
Изображение Александра Dulaunoy через Flickr