На главную   ::   Содержание



Алгоритмы работы со стеками, очередями и деками в последовательном и связном представлении

Определение 1.   Стек -- это упорядоченное динамическое множество, для которого операции удаления и добавления элемента определены по принципу LIFO (last-in, first-out). То есть удалить можно только тот элемент, который был добавлен последним.

Определение 2.   Очередь -- это упорядоченное динамическое множество, для которого операции удаления и добавления элемента определены по принципу FIFO (first-in, first-out). То есть удалить можно только тот элемент, который находился в очереди дольше всего.

В последовательном представлении удобно реализовать эти структуры данных с помощью массива. Пусть есть массив $ S[1..N]$. Для управления стеком заведем переменную $ top$, которая хранит индекс последнего добавленного элемента (если $ top=0$, то стек пуст). Определим операции PUSH (добавить элемент $ x$ в стек) и POP (удалить элемент из стека).

24pt PUSH

24pt
1
$ top\leftarrow top+1$
2
$ S[top]\leftarrow x$

24pt POP

24pt
1
if $ top=0$ then error(«стек пуст»)
2
$ x\leftarrow S[top]$
3
$ top \leftarrow top-1$
4
return $ x$

Для реализации очереди определим массив $ Q[1..N]$ и две переменные: $ head$ и $ tail$ -- «голова» и «хвост» очереди. Считаем, что $ head$ указывает на элемент, который будет извлечен следующим. $ tail$ указывает на первую свободную ячейку, куда может быть помещен следующий добавляемый элемент. Если $ head=tail$, то очередь пуста (изначально пусть $ head=tail=0$). Очередь передвигается по массиву циклически. Возможность переполнения не отслеживается. Определим аналогичные опереции добавления и удаления для очереди.

24pt PUSH

24pt
1
$ Q[tail]\leftarrow x$
2
if $ tail=N$ then $ tail\leftarrow 1$
3
else $ tail\leftarrow tail+1$

24pt POP

24pt
1
if $ head=tail$ then error(«очередь пуста»)
2
$ x\leftarrow Q[head]$
3
if $ head=N$ then $ head\leftarrow 1$
4
else $ head \leftarrow head+1$
5
return $ x$

Определение 3.   Дек -- это упорядоченное динамическое множество, для которого операции удаления и добавления элемента определены по принципу стека и очереди одновременно. То есть удалить и добавить элемент можно с любого конца.

Дек несложно реализуется по аналогии со стеком и очередью. Только нужно четыре операции -- добавление и удаление с обоих концов.

Связное представление -- это представление с помощью связного списка.

Определение 4.   Список -- структура данных для хранения упорядоченного множества. Каждый элемент имеет указатель(указатели) на другой (другие) элемент (элементы) списка.

Как правило (обозначим через $ L$ некоторый список), имеется два специальных указателся $ head[L]$ -- начало списка и $ tail[L]$ -- конец списка. Каждый элемент списка $ x\in L$ имеет значение $ key[x]$ -- некоторые данные (например, число). Для поддержки порядка вводится поле $ next[x]$ -- элемент следующий за $ x$ в списке $ L$. Такой список называется односвязным (каждый человек в очереди помнит только того, кто перед ним). Список называется двусвязным, если кроме $ next[x]$ определено значение $ prev[x]$ -- предшествующий $ x$ в списке $ L$ (если человек в очереди будет помнить и того, за кем он стоит и того, кто стоит за ним). Если $ next[x]$ ($ prev[x]$) не определено для некоторого $ x\in L$, то элемент $ x$ не имеет следующего (предшествующего). Если $ head[L]$ не определен, то список пуст (когда переменная, например $ a$, не определена, мы пишем $ a=NULL$)

Реализуем, например, стек (нам нужен лишь односвязный список).

24pt PUSH

24pt
$ \rhd$
Создаем новый элемент списка, содержащий информацию $ x$
1
$ z\leftarrow \textbf{new}(x) $
$ \rhd$
Определяем порядок нового элемента (он теперь будет в начале списка)
2
if $ head[L]=NULL$ then $ head[L]\leftarrow z$
3
else
4
$ next[z]\leftarrow head[L]$
5
$ head[L]\leftarrow z$

24pt POP

24pt
1
if $ head[L]=NULL$ then error(«пусто»)
2
$ z\leftarrow head[L]$
3
$ head[L]\leftarrow next[head[L]]$
3
$ x\leftarrow key[z]$
3
delete $ z$
4
return x

Для реализации очереди или дека уже понадобится двусвязный список. Сама реализация аналогична; главное -- правильно управлять ссылками на соседей.

В различных случаях удобнее пользоваться разными способами представления. Но перечислим основные моменты, на которые обращают внимание при выборе реализации:



На главную   ::   Содержание