Рис. 11.1 Реализация стека на базе массива S. Светло-серые клетки заняты элементами стека, (а) Стек S содержит 4 элемента, верхний элемент - число 9. (б) Тот же стек после выполнения операций Push(5, 17) и Push(5, 3). (в) Стек после того, как операция Pop(S) вернула значение 3 (последний добавленный в стек элемент). Хотя число 3 по-прежнему присутствует в массиве S, в стеке его уже нет; на вершине стека - число 17.

S[l] - нижний элемент стека («дно») a SftopfS]] - верхний элемент, или вершина стека.

Если topfS*] = 0, то стек пуст (is empty). Если topfS*] = га, то при попытке добавить элемент происходит переполнение (overflow), поскольку размер стека в нашей реализации ограничен числом га. Симметричная ситуация - попытка удалить элемент из пустого стека - по-русски никак не называется («недо-полнение»?), а по-английски называется underflow. В этой главе для простоты мы не будем обращать внимание на возможность переполнения стека.

Операции со стеком (проверка пустоты, добавление элемента, удаление элемента) записываются так:

Stack-Empty (5)

1if top[S] = О

2then return true

3else return false

Push(S, x)

1top[S] <- top[S] + 1

2S[top[S]] <r- x

Pop(S)

1if Stack-Empty(S)

2then error "underflow"

3else topfS*] <- topfS*] - 1

4return SftopfS] + 1]

Выполнение операций Push и Pop показано на рис. 11.1. Каждая из трёх операций со стеком выполняется за время 0(1).

Очереди

Операцию добавления элемента к очереди мы будем обозначать Enqueue, а операцию удаления элемента из очереди будем обозначать Dequeue. (Как и для стеков, удаляемый из очереди элемент определен однозначно и поэтому является не передаётся процедуре процедуре Dequeue, а возвращается этой процедурой.) Правило здесь такое же, как в живой очереди: первым пришёл - первым обслужен. (И если наши программы правильны, можно не опасаться, что кто-то пройдёт без очереди.)

Другими словами, у очереди есть голова (head) и хвост (tail). Элемент, добавляемый в очередь, оказывается в её хвосте, как только что подошедший покупатель; элемент, удаляемый из очереди, находится в её голове, как тот покупатель, что отстоял дольше всех.

На рис. 11.2 показано, как можно реализовать очередь, вмещающую не более чем п-1 элемент, на базе массива Q[l. .п]. Мы храним числа head[Q] - индекс головы очереди, и tail[Q] - индекс свободной ячейки, в которую будет помещён следующий добавляемый к очереди элемент. Очередь состоит из элементов массива, стоящих на местах с номерами head[Q], head[Q] + 1, ... , tail[Q] - 1 (подразумевается, что массив свёрнут в кольцо: за п следует 1). Если head[Q] = tail[Q], то очередь пуста. Первоначально имеем head[Q] = tail[Q] = 1. Если очередь пуста, попытка удалить элемент из неё ведёт к ошибке (underflow); если head[Q] = tail[Q]-\-l, то очередь полностью заполнена, и попытка добавить к ней элемент вызовет переполнение (overflow).

В наших реализациях процедур Enqueue и Dequeue мы игнорируем возможность переполнения или попытки изъятия элемента из пустой очереди (в упражнении 11.1-4 мы попросим вас внести в код соответствующие проверки).

Enqueue(Q,ж)

1Q[tail[Q]] <г- ж

2if tail[Q] = length[Q]

3then tail[Q] <- 1

4else tail[Q] <- tail[Q] + 1

Dequeue(Q)

1ж <- Q[/jead[Q]]

2if head[Q] = length[Q]

3then head[Q] <- 1

4else head[Q] <- head[Q] + 1

5return ж

Работа процедур Enqueue и Dequeue показана на рис. 11.2.

Рис. 11.2 Очередь, реализованная на базе массива Q[l. . п]. Светло-серые клетки заняты элементами очереди, (а) В очереди находятся 5 элементов (позиции Q[7..11]). (б) Очередь после выполнения процедур Enqueue(Q, 17), ENqueue, 3) и Enqueue(Q, 5). (в) Очередь после выполнения процедуры dequeue) (которая возвращает значение 15). Новой головой очереди стало число 6.

Каждая из этих процедур работает за время 0(1). Упражнения

11.1-1 Следуя образцу рис. 11.1, покажите работу операций Push(S, 4), Push(S, 1), Push(S, 3), Рор(5), Push(S, 8) и Pop(S) на стеке, реализованном с помощью массива 5*[1..6]. Первоначально стек пуст.

11.1-2 Как на базе одного массива А[1.. га] реализовать два стека суммарной длины не больше га? Операции Push и Pop должны выполняться за время 0(1).

11.1-3 Следуя образцу рис. 11.2, покажите работу операций Enqueue(Q, 4), Enqueue(Q, 1), Enqueue(Q, 3), Dequeue(Q), Enqueue(Q, 8) и Dequeue(Q) на очереди, реализованной с помощью массива Q[l. .5]. Первоначально очередь пуста.

11.1-4 Перепишите процедуры Enqueue и Dequeue, предусмотрев проверки на случай переполнения или underflow.

11.1-5 Стек позволяет добавлять и удалять элементы только с одного конца. В очередь добавлять элементы можно только с одного конца, а удалять - только с другого. Структура данных, называемая деком (deque, от double-ended queue - «очередь с двумя