Вступление
Каждый разработчик знает, что компьютерные алгоритмы тесно связаны со структурами данных. Действительно, многие из алгоритмов зависят от структур данных и могут быть очень эффективными для одних структур данных и неэффективными для других. Типичным примером этого является алгоритм heapsort, который зависит от структуры данных, называемой «куча». В этом случае, хотя стек и очередь являются структурами данных, а не чистыми алгоритмами, важно понимать их структуру и то, как они работают с данными.
Однако, прежде чем мы продолжим конкретную реализацию стека и очереди, давайте сначала посмотрим на определение этого термина. Структура данных — это логическая абстракция, которая «моделирует» реальный мир и представляет (хранит) наши данные в определенном формате. Доступ к этой структуре данных часто предопределен, поэтому мы можем получить доступ непосредственно к каждому элементу, содержащему данные. Это помогает нам выполнять различные виды задач и операций над различными типами структур данных — вставка, удаление, поиск и т. Д. Типичными структурами данных являются стек, очередь, связанный список и дерево.
Все эти структуры помогают нам эффективно выполнять определенные операции. Например, поиск в сбалансированном дереве быстрее, чем поиск в связанном списке.
Также очень важно отметить, что структуры данных могут быть представлены разными способами. Мы можем смоделировать их, используя массивы или указатели, как показано в этом посте. На самом деле самое важное — представить логическую структуру структуры данных, которую вы моделируете. Таким образом, стек является структурой, которая следует принципу LIFO (Last In First Out), и не имеет значения, как он представлен в нашей программе (будет ли он кодироваться с помощью массива или указателей). В представлении стека важно правильно следовать принципу LIFO. В этом случае, если стек является массивом, должна быть доступна только его вершина, и единственной операцией должна быть вставка новой вершины стека.
обзор
Стек и очередь как-то связаны между собой структурами данных, поскольку они представляют две части каким-то образом идентичных логик. Таким образом, они обычно описываются в паре.
стек
Структура данных стека моделирует реальный стек. Вы можете думать об этом как о стеке коробок один над другим. Таким образом, единственный способ поместить другой элемент в стек — поместить его выше всех других элементов (на его вершине). Эту операцию часто называют «толкать». С другой стороны, взятие предмета из стека называется «поп», и «только высший предмет» может быть «выброшен». Следующее изображение лучше описывает структуру стека и его операций — push и pop.
Операции вставки и удаления элемента из стека обычно называются push и pop!
Мы видим здесь, как компьютерные структуры данных моделируют реальный мир. Структура данных стека действительно не является исключением и моделирует реальные стеки.
Реализация стека
Как я уже сказал, стек может быть реализован разными способами. Первый подход заключается в использовании массива (с использованием определенного языкового синтаксиса языка программирования по вашему выбору). Вот реализация стека с использованием массива в PHP .
$stack = array();
function push($data, &$stack) {
$stack[] = $data;
}
function pop(&$stack)
{
$len = count($stack);
$top = $stack[$len-1];
unset($stack[$len-1]);
return $top;
}
// array()
print_r($stack);
push(1, $stack);
push(2, $stack);
push('some test', $stack);
push(array(25,12,1999), $stack);
// [1, 2, 'some test', [25, 12, 1999]]
print_r($stack);
// [25, 12, 1999]
echo pop($stack);
// 'some test'
echo pop($stack);
// [1, 2]
print_r($stack);
Однако есть намного более простые способы сделать то же самое с PHP, так как есть много предопределенных функций, которые работают со стеками.
$stack = array();
function push($data, &$stack) {
$stack[] = $data;
}
function pop(&$stack)
{
return array_pop($stack);
}
// array()
print_r($stack);
push(1, $stack);
push(2, $stack);
push('some test', $stack);
push(array(25,12,1999), $stack);
// [1, 2, 'some test', [25, 12, 1999]]
print_r($stack);
// [25, 12, 1999]
echo pop($stack);
// 'some test'
echo pop($stack);
// [1, 2]
print_r($ret);
Как и во многих языках программирования здесь, в примере используются целые числа, но его можно модифицировать для работы с более сложными типами данных, такими как объекты, многомерные массивы и т. Д. Однако мы можем использовать абстракцию более высокого уровня для представления стека. Вот краткий пример стека с использованием указателей. Класс стека содержит только указатель на вершину стека. Таким образом, только верх может быть «всплывающим». Также каждый элемент указывает на своего предшественника. Используя эту абстракцию, мы уверены, что программист может выполнять только эти две операции — «pop» и «push».
class Struct
{
protected $_data = null;
protected $_next = null;
public function __construct($data, $next)
{
$this->_data = $data;
$this->_next = $next;
}
public function getData()
{
return $this->_data;
}
public function setData(&$data)
{
$this->_data = $data;
}
public function getNext()
{
return $this->_next;
}
public function setNext(&$next)
{
$this->_next = $next;
}
}
class Stack
{
protected $_top = null;
public function push($data)
{
$item = new Struct($data, null);
if ($this->_top == null) {
$this->_top = $item;
} else {
$item->setNext($this->_top);
$this->_top = $item;
}
}
public function pop()
{
if ($this->_top) {
$t = $this->_top;
$data = $t->getData();
$this->_top = $this->_top->getNext();
$t = null;
return $data;
}
}
public function __toString()
{
$output = '';
$t = $this->_top;
while ($t) {
$output .= $t->getData() . ' ';
$t = $t->getNext();
}
return $output;
}
}
$s = new Stack();
$s->push(1);
$s->push(2);
$s->push(3);
// 3 2 1
echo $s;
$s->pop();
$s->pop();
// 1
echo $s;
Очередь
Как упоминалось выше, очередь как-то связана со структурой данных стека. Однако он следует другому принципу — FIFO («первым пришел — первым обслужен»), что означает, что элемент, который находился в очереди в течение самого длительного времени, извлекается первым.
Вставка и удаление из очереди происходят на противоположных участках очереди!
Это снова из реального мира, где мы можем думать об очереди людей, ожидающих перед кинотеатром. В этом случае человек, который ждал больше всего, сначала берет свой билет.
Реализация очереди
Представление массива в очередь не является сложной задачей. Однако единственный пример очереди здесь — это использование указателей. Действительно, следующий синтаксис кода очень тесно связан с PHP, поэтому важны только основные принципы поддержки функциональности очереди.
class Item
{
public $data = null;
public $next = null;
public $prev = null;
public function __construct($data)
{
$this->data = $data;
}
}
class Queue
{
protected $_head = null;
protected $_tail = null;
public function insert($data)
{
$item = new Item($data);
if ($this->_head == NULL) {
$this->_head = $item;
} else if ($this->_tail == NULL) {
$this->_tail = $item;
$this->_head->next = $this->_tail;
$this->_tail->prev = $this->_head;
} else {
$this->_tail->next = $item;
$item->prev = $this->_tail;
$this->_tail = $item;
}
}
public function delete()
{
if (isset($this->_head->data)) {
$temp = $this->_tail;
$data = $temp->data;
$this->_tail = $this->_tail->prev;
if (isset($this->_tail->next))
$this->_tail->next = null;
else
$this->_tail = $this->_head = null;
return $data;
}
return FALSE;
}
public function __toString()
{
$output = '';
$t = $this->_head;
while ($t) {
$output .= $t->data . ' | ';
$t = $t->next;
}
return $output;
}
}
$q = new Queue();
$q->insert(1);
$q->insert(2);
$q->insert(3);
// 1 2 3
echo $q;
$q->delete();
$q->delete();
// 1
echo $q;
$q->insert(15);
$q->insert('hello');
$q->insert('world');
$q->delete();
// 1 15 "hello"
echo $q;
заявка
Стеки и очереди широко используются в программировании. Определяя стеки и очереди, мы каким-то образом предопределяем способ доступа к нашей структуре данных, поэтому мы уверены, что наша программа получит доступ к данным особым образом. Например, если мы закодируем очередь для списка или последующих команд, мы уверены, что наиболее ожидаемая команда будет выполнена первой. В этом случае мы заранее определяем порядок обработки команд. В веб-программировании, особенно в JavaScript, каждый разработчик знает, что происходит в веб-браузере environemtn. В случае многих событий они помещаются в очередь и выполняются последовательно в том порядке, в котором они были запущены пользователем.
Другим примером является стек выполнения большинства программных компиляторов и интерпретаторов. Мы знаем, что в языках ООП, таких как, например, PHP, есть стек вызовов функций. В случае неудачи мы можем легко увидеть «трассировку стека».
Вы видите, сколько примеров очередей и стеков существует в реальном программировании. Эти две структуры легко реализовать, но они очень важны для понимания других более сложных структур данных как связанных списков и деревьев.