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

Стэки
В обычной жизни, стек представляет собой набор объектов, которые сложены друг на друге – к примеру, за стек можно взять книги на полке или горы тарелок в школьной столовой. Если говорить о программировании, стек - это коллекция объектов, обладающая определёнными свойствами, где последний вставленный объект будет удалён первым, при необходимости. Данное свойство называется LIFO («последним пришёл — первым ушёл»). Конфетные и сигаретные автоматы действуют точно по такому же принципу.

Если говорить абстрактно, то стек - это линейная последовательность элементов, где добавление (“push”) и удаление (“pop”) элементов происходят вокруг “верхушки” стека. Основные операции:

init – создание стека.
push – добавление элемента на верхушку стека.
pop – удаление элемента с верхушки стека.
top – получить доступ к верхнему элементу стека, не удаляя его.
isEmpty – проверка на присутствие элементов в стеке.

Стек может быть реализован таким образом, чтобы быть максимально ёмкими. Если в стеке не осталось свободного места, то говорится что стек заполнен.

Поскольку стек обладает свойством LIFO, то на PHP его реализовать очень просто, используя массивы и специальные функции push и pop.

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

<?php
class ReadingList
{
    protected $stack;
    protected $limit;
 
    public function __construct($limit = 10) {
        $this->stack = array();
        $this->limit = $limit;
    }
 
    public function push($item) {
        if (count($this->stack) < $this->limit) {
 
            array_unshift($this->stack, $item);
        } else {
            throw new RunTimeException('Stack is full!');
        }
    }
 
    public function pop() {
        if ($this->isEmpty()) {
          throw new RunTimeException('Stack is empty!');
      } else {
            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(), так что последний вставленный элемент всегда будет сверху.

Давайте добавим парочку элементов в стек:

<?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(); // выводит 'A Game of Thrones'
echo $myBooks->pop(); // выводит 'A Clash of Kings'
echo $myBooks->pop(); // выводит 'A Storm of Swords'

Посмотрим что на верхушке:

<?php
echo $myBooks->top(); // выводит 'A Feast for Crows'

Что будет, если удалить?

<?php
echo $myBooks->pop(); // выводит 'A Feast for Crows'

А если добавить ещё один элемент?

<?php
$myBooks->push('The Armageddon Rag');
echo $myBooks->pop(); // выводит 'The Armageddon Rag'

Если мы попытаемся удалить элемент из стека, когда тот уже пуст, то получим следующее сообщение.

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

Добавлено: 08 Мая 2018 12:07:24 Добавил: Андрей Ковальчук Нравится 0

Добавить