Линейные списки: стеки, очереди и деки

Будем рассматривать не только структуру данных, но и операции, которые выполняются с этими данными.

Линейный список — это множество, состоящее из n> 0 узлов X [1], X [2], ..., X [n],

если n >0, то X [1] является первым узлом; если l< k <. n, то k-му узлу X [k] предшествует X [k -1] и за ним следует X [k + 1]; X [n] является последним узлом.

Операции, которые мы можем выполнять с линейными списками, включают, например, следующие:

• Получить доступ к k-му узлу списка, чтобы проанализировать и/или изменить содержимое его полей.
• Включить новый узел непосредственно перед k-м узлом.
• Исключить k-й узел.
• Объединить два (или более) линейных списка в один список.
• Разбить линейный список на два (или более) списка.
• Сделать копию линейного списка.
• Определить количество узлов в списке.
• Выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах.
• Найти в списке узел с заданным значением в некотором поле.

Очень часто встречаются линейные списки, в которых включение, исключение или доступ к значениям почти всегда производятся в первом или последнем узлах, и мы дадим им специальные названия:

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

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

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

Из стека мы всегда исключаем "младший" элемент из имеющихся в списке, т. е. тот, который был включен позже других.

Для очереди справедливо в точности противоположное правило: исключается всегда самый "старший" элемент; узлы покидают список в том порядке, в котором они в него вошли.

Стек называли пуш-даун (push-down) списком, реверсивной памятью, гнездовой памятью, магазином, списком типа LIFO ("last-in-first-out" — "последним включается — первым исключается). Очередь иногда называют — циклической памятью или списком типа FIFO ("first-in-first-out" — "первым включается — первым исключается").

Стек, представленный в виде железнодорожного разъезда. •

Процесс входов в подпрограммы и выходов из них при выполнении машинной программы подобен процессу функционирования стека. Стеки особенно полезны при обработке языков программирования и арифметических выражений. Вообще, стеки чаще всего возникают в связи с алгоритмами, имеющими явно или неявно рекурсивный характер.