Стек

Стек (stack) — это линейная структура данных, в которой элементы добавляются и удаляются только с одного конца — вершины стека. Можно представить себе стек как стопку тарелок. Вы можете положить новую тарелку на вершину стопки, можете снять верхнюю тарелку со стопки, но только верхнюю. Если вам нужно добраться до нижней тарелки, то есть до самого первого элемента стека, вы должны убрать из стопки все тарелки, причём одну за другой.

То есть если мы положим в стек последовательно числа \(1\), \(2\), \(3\), а потом удалим из стека последний элемент, то в стеке останутся числа \(1\) и \(2\). Если мы затем положим в стек числа \(4\) и \(5\) и будем последовательно удалять из стека элементы, то элементы будут удаляться в порядке \(5\), \(4\), \(2\), \(1\).

Таким образом, стек поддерживает следующие операции:

  • Добавить элемент в конец стека (push)
  • Узнать значение последнего элемента стека (top)
  • Удалить последний элемент из стека (pop)
  • Узнать размер стека

Все эти операции в стеке выполняются за \(O(1)\).

В плюсах, как и во многих языках, есть встроенная реализация стека \(std::stack\). Примечательно, что по стандарту он целиком и полностью наследуется от дека.

Очередь

Другая структура данных, похожая на стек, — это очередь (queue). Её назначение понятно из названия. Элементы выстраиваются один за другим, новые элементы добавляются в конец очереди, а удаляются элементы из начала очереди.

Очередь поддерживает следующие операции:

  • Добавить элемент в конец очереди (push)
  • Удалить элемент из начала очереди (pop)
  • Узнать значение первого элемента очереди (front)
  • Узнать размер очереди (size)

Все операции с очередью должны выполняться за \(O(1)\).

В плюсах, как и во многих языках, есть встроенная реализация очереди \(std::queue\). Примечательно, что по стандарту она целиком и полностью наследуется от дека.

Дек

Если есть стек, в который элементы кладутся в один конец и извлекаются с того же конца, и очередь, в которой элементы кладутся в один конец, а извлекаются с другого конца, то логичным кажется существование структуры данных, которая называется дек, по английски deque или double-ended queue.

Дек поддерживает следующие операции:

  • Добавить элемент в начало дека
  • Добавить элемент в конец дека
  • Удалить элемент из начала дека
  • Удалить элемент из конца дека
  • Узнать значение последнего элемента дека
  • Узнать значение первого элемента дека
  • Узнать размер дека

Все операции должны выполняться за \(O(1)\) или в среднем за \(O(1)\).

В плюсах есть готовая реализация \(std::deque\).

Интересной особенностью реализации дека в C++ является то, что вы можете обратиться к элементу дека по индексу, как к элементам массива. Например, если в деке \(d\) будет 5 элементов, то к ним можно обращаться как \(d[0]\), \(d[1]\), …., \(d[4]\). Это обращение будет выполняться за \(O(1)\), но будет чуть медленнее, чем обращение к элементам вектора или массива.