Стеки, очереди, деки

Разберем разновидности линейных списков, в которых доступ к элементам осуществляется только с концов.

Стек — линейный список, в котором вставка и удаление выполняются только на одном конце.

Очередь — линейный список, в котором вставка происходит в один конец, а удаление (извлечение) из другого конца.

Дек — линейный список, в котором доступ, вставка и удаление могут выполняться на обоих концах. Дек, получается, может выполнять функции и стека, и очереди.

Стек

Элементы в стеке организованы по принципу LIFO (последним вошел — первым вышел). Извлекаются элементы из стека в порядке от младшего к старшему, то есть первым будет извлекаться тот элемент, который был вставлен в стек позже всех.

Можно представить стек как стопку тарелок: класть новую тарелку можно только на верх стопки и забирать тарелки можно только с верху стопки. Из середины тарелки вытаскивать нельзя.

Когда элемент помещается в стек, говорят, что элемент кладётся на верх стека, и забирается, соответственно, тоже с верха. Просто удобная терминология.

Интерфейс стека состоит из трех методов

empty() — проверка, является ли стек пустым

push(value) — помещение value на верх стека

pop() -> value — извлечение объекта с верха стека

Для стека, содержащего $n$ элементов, потребуется в любом случае память $\Theta(n)$ , ведь все эти элементы надо как-то хранить.

Стек на массиве

Очередь

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

Очередь, собственно, работает как нормальная человеческая очередь. Человек, который раньше в эту очередь встал, раньше из нее выйдет.

Когда элемент помещается в очередь, говорят, что элемент в очередь заходит, а при извлечении элемента из очереди он из неё выходит. Уже не такая интуитивная терминология, как у стека, но тоже ничего.

Дек

В деке все операции с элементами могут выполняться с обоих концов. Концы традиционно называют правым и левым.

Упражнения

Покажите, что с помощью стека можно получить перестановку $(\sigma_1, \sigma_2, \dotsc, \sigma_n)$ чисел $(1, 2, \dotsc, n)$ только в том случае, если не существует таких индексов $i < j < k$ таких, что $\sigma_j < \sigma_k < \sigma_i$ .