2. Стеки и очереди

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

В обоих случаях операции включения и исключения производятся только на концах последовательности [3].

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

Правило работы со стеком: «Первым пришел — последним ушел».

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

Правило работы с очередью: «Первым пришел — первым ушел».

Стеки и очереди имеют важное значение в бухгалтерском деле.

Введем следующие обозначения:

D  X Добавить X к D. Если D — стек, то X помещается в вершину, если D — очередь, то Х добавляется в ее конец.

X  D Присвоить переменной Х значение верхнего элемента D, если D — стек, или начального элемента, если D — очередь. Этот элемент затем из D исключается.

Последовательная реализация списков

Для стеков это распределение весьма удобно. Все, что нам нужно, это переменная, например t, чтобы следить за вершиной стека S. Предположим, что для S отведены ячейки S(1), S(2), …, S(m), тогда пустой стек соответствует случаю t = 0. Операции включения и исключения в стек при этом следующие:

S  X tt+1 if t>m then overflow {переполнение} else s(t)  X

X  S if t=0 then underflow {нехватка} else X  S(t)

t  t-1

Здесь overflow означает переполнение или отсутствие в стеке места для добавления X, что означает ошибку.

Underflow означает, что делается попытка удалить элемент из пустого стека, как правило, этот оператор означает окончание алгоритма.

Последовательное распределение очереди сложнее потому, что она растет на одном конце и убывает на другом.

Если ничего не предпринимать, то очередь начнет медленно двигаться и перейдет границу отведенных для нее ячеек. Чтобы это не произошло для очереди Q будем использовать m ячеек Q(0), Q(1), …, Q(m-1), связанных круговым способом, и считаем, что Q(0) следует за Q(m-1). Если использовать переменную f в качестве указателя ячейки, расположенной непосредственно перед началом очереди, а переменную r в качестве указателя ее конца, то очередь будет состоять из элементов Q(f+1), Q(f+2), …, Q(r). Согласно этому определению, пустая очередь соответствует случаю r = f. Мы имеем:

Q  X r  r+1 {ограничено величиной m} if r > m then overflow else Q(r)  X

X  Q if r = f then underflow else X  Q(f)

f  f+1

3. Организация связанного распределения на основе стеков и очередей

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

Нижний элемент стека имеет пустой указатель  в поле LINK, и t =  означает пустой стек. Итак, имеем:

S  X new(l); {заводится ячейка памяти} INFO(l)  X LINK(l)  t {t — вершина стека} t  l

X  S if t =  then underflow else X  INFO(t)

t  LINK(t)

Для очередей связанного распределения справедливо:

Q  X new(l);

INFO(l)  X

LINK(l)  f

{организация цикла}

LINK(r)  l r  l

X  Q if f =  then underflow else X  INFO(f)

LINK(r)LINK(f)