Цикл «Проще простого™» поможет познать очень простые вещи.
Сегодня мы рассмотрим два простых контейнера — это очередь (queue) и стек (stack). Так как данные простые вещи действительно являются простыми, то они не нуждаются в дальнейшем разъяснении: все комментарии приведены в самом коде. Примеры написаны на PHP.
Очередь
/*
* Очередь очень похожа на стек, но также похожа и на реальную очередь.
* Реализуется она по принципу FIFO.
* FIFO значит, что элемент, пришедший первым, первым и покинет контейнер.
* Данный класс является простейшей реализацией очереди.
*/
class Queue
{
//Элементы очереди
private $Elements;
//Конструктор
public function __construct()
{
$this->Elements = Array();
}
//Добавить элемент в очередь
public function Insert($element)
{
array_push($this->Elements, $element);
}
//Удалить последний элемент из очереди
public function Remove()
{
if ($this->GetSize() != 0)
return array_shift($this->Elements);
}
//Запросить первый элемент очереди (пришешдий последним)
public function RetreiveFirst()
{
return $this->Elements[0];
}
//Запросить последний элемент очереди (пришешдий первым)
public function RetreiveLast()
{
return end($this->Elements);
}
//Получение количества элементов в очереди
public function GetSize()
{
return count($this->Elements);
}
}
Попробуем!
//Создаём очередь
$MyQueue = new Queue();
//Добавляем элементы в очередь
$MyQueue->Insert(5); //В очереди: 5
$MyQueue->Insert(12); //В очереди: 5 12
$MyQueue->Insert(20); //В очереди: 5 12 20
//Получаем первый и последний элементы
echo $MyQueue->RetreiveFirst(); //Результат: 5
echo $MyQueue->RetreiveLast(); //Результат: 20
//Удаляем элементы из очереди
$MyQueue->Remove(); //В очереди: 12 20
$MyQueue->Remove(); //В очереди: 20
Стек
/*
* Стек реализуется по принципу FILO.
* FILO значит, что элемент, который приходит первым, покидает контейнер последним.
* Из стека мы можем получить только вершину, остальные части стека мы видеть не можем.
* Данный класс является самой простой реализацией стека на PHP.
*/
class Stack
{
//Элементы стека
private $Elements;
//Конструктор
public function __construct()
{
$this->Elements = Array();
}
//Добавление элемента в стек
public function Push($element)
{
array_push($this->Elements, $element);
}
//Запрос верхушки стека
//Не удаляет верхний элемент
public function RetreiveTop()
{
return end($this->Elements);
}
//Запрос верхушки стека и удаление его
public function Pop()
{
if ($this->GetSize() != 0)
return array_pop($this->Elements);
}
//Получение количества элементов в стеке
public function GetSize()
{
return count($this->Elements);
}
}
Проверяем стек
//Создаём стек (верхушка стека сейчас не существует [равна нулю])
$MyStack = new Stack();
//Добавляем элементы в стек
$MyStack->Push(5); //В стеке: 5 [верхушка]
$MyStack->Push(12); //В стеке: 12 [верхушка], 5
$MyStack->Push(20); //В стеке: 20 [верхушка], 12, 5
//Получаем верхушку (последний добавленный элемент, но не удаляем)
echo $MyStack->RetreiveTop(); //Результат: 20
//Получаем верхушку, удаляя её из стека (поднимая все предыдущие элементы)
$MyStack->Pop(); //В стеке: 12 [верхушка], 5
$MyStack->Pop(); //В стеке: 5 [верхушка]
$MyStack->Pop(); //В стеке: стек пуст
На сегодня всё. Продолжения обязательно будут. Всем удачного дня!
