Понятие списковой структуры. Стек как полустатическая структура. Операция над стеками

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

Списки

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

Пример списка:

E₁, E₂,........, E_n,... n > 1 и не зафиксировано.

Количество элементов списка может меняться в процессе выполнения программы. Различают 2 вида списков:

1) Несвязные

2) Связные

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

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

Стеки

Очередь вида LIFO (Last In First Out - Последним пришел, первым ушел), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним, называется стеком. Это одна из наиболее употребляемых структур данных, которая оказывается весьма удобной при решении различных задач.

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

Графически стек можно представить следующим образом:

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

Операции, производимые над стеками:

1. Занесение элемента в стек.

Push(S,I), где S - идентификатор стека, I - заносимый элемент.

2. Выборка элемента из стека.

Pop(S)

3. Определение пустоты стека.

Empty(S)

4. Прочтение элемента без его выборки из стека.

StackTop(S)

5. Определение переполнения стека (для полустатических структур)

Full(S)

Алгоритмы основных операций со стеком

Обозначим i - указатель вершины

 

Push(S,x)

i = i+1

S(i) = x

return

 

Pop(S)

x = S(i)

i = i -1

return

 

Empty(S)

if i = 0

then “пусто”

Stop

return

endif

 

Full(S)

if i = maxS

then “переполнение”

Stop

return

endif

StackTop(S)

x = S(i)

return

Заметим, что при выборки элемента из стека для обеспечения корректности выполняемой операции необходимо проверять стек на пустоту, поэтому абсолютно правильный алгоритм для функции Pop(S) будет следующим

Pop(S)

if i = 0 then “пусто”

Stop

return

endif

x = S(i)

i = i -1

return

Алгоритм проверки стека на пустоту можно записать несколько по другому, если использовать логический тип данных

Empty(S)

if i = 0 then empty = true

else empty = false

endif

return

Затем можно изменить алгоритм функции Pop(S)

Pop(S)

Empty(S)

if empty = true

then “пусто”

Stop

return

endif

x = S(i)

i = i -1

return

Наконец, полностью корректный алгоритм занесения нового элемента в реализованный на массиве полустатический стек обязательно должен предусматривать проверку на переполнение, соответственно приведем правильный алгоритм операции Push(S,i)

Push(S,i)

if i = maxS

then “переполнение”

Stop

return

endif

i = i+1

S(i) = x

return

Понятно, что maxS здесь максимальное число элементов массива.

 

Очередь как полустатическая структура. Операции над очередью.

Очередь

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

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

На рисунке ниже приведена очередь, содержащая четыре элемента — А, В, С и D. Элемент А расположен в начале очереди, а элемент D — в ее конце. Элементы могут удаляться только из начала очереди, то есть первый помещаемый в очередь элемент удаляется первым. По этой причине очередь часто называют списком, организованным по принципу «первый размещенный первым удаляется» в противоположность принципу стековой организации — «последний размещенный первым удаляется».

Дисциплину обслуживания, в которой заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди), называется FIFO (First In First Out - Первым пришел, первым ушел). Очередь открыта с обеих сторон.

Таким образом, изъятие компонент происходит из начала очереди, а запись- в конец. В этом случае вводят два указателя: один - на начало очереди, второй- на ее конец.

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

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

Операции, производимые над очередью:

Для очереди определены три операции. Операция insert (q,x) помещает элемент х в конец очереди q. Операция remove(q) удаляет элемент из начала очереди q и присваивает его значение переменной х. Третья операция, empty (q), возвращает значение true или false в зависимости от того, является ли данная очередь пустой или нет. Кроме того. Учитывая то, что полустатическая очередь реализуется на одномерном массиве, необходимо следить за возможностью его переполнения. С этой целью вводится четвертая операция full(q).

Операция insert теоретически может быть выполнена всегда, поскольку на количество элементов, которые может содержать очередь, никаких ограничений не накладывается. На практике для полустатической очереди, конечно же, накладываются ограничения, так как количество элементов в массиве всегда конечное. Операция remove применима только к непустой очереди, поскольку невозможно удалить элемент из очереди, не содержащей элементов. Результатом попытки удалить элемент из пустой очереди является возникновение исключительной ситуации потеря значимости. Операция empty, разумеется, выполнима всегда.

Для очереди вводят два указателя: один - на начало очереди (F), второй- на ее конец (R).

Если очередь пуста, то F = 1, а R = 0. Данные значения являются начальными. R < F – условие пустоты очереди.

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

Full (q)

if R = maxQ then full = true

else full = false

endif

return

 

Empty (q)

if R < F then empty = true

else empty = false

endif

return

 

Insert (q, x)

Full (q)

if full = true then ‘переполнение’

stop

return

endif

R = R + 1

q(R) = x

return

 

Remove (q)

Empty (q)

if empty = true then ‘пусто’

stop

return

endif

x = q(F)

F = F + 1

return

Рассмотрим теперь примеры работы с очередью с использованием стандартных функций. Для реализации очереди будем использовать небольшой массив из 5 элементов.

maxQ = 5

R = 0, F = 1

Условие пустоты очереди R < F (0 < 1)

Произведем вставку элементов A, B и C в очередь:

Insert (q, A);

Insert (q, B);

Insert (q, C);

Убираем элементы A и B из очереди:

Remove (q);

Remove (q);

Добавляем элементы D и E:

Insert (q, D);

Insert (q, E);

Убираем элементы С,D и E из очереди:

Remove (q);

Remove (q);

Remove (q).

Возникла абсурдная ситуация, при которой очередь является пустой (R < F), однако новый элемент разместить в ней нельзя, так как R = maxQ.

Одним из решений возникшей проблемы может быть модификация операции Remove (q) таким образом, что при удалении очередного элемента вся очередь смещается к началу массива. Переменная F больше не требуется, поскольку первый элемент массива всегда является началом очереди. Пустая очередь представлена очередью, для которой значение R равно нулю.

 

Произведем вставку элементов A, B и C в очередь:

Insert (q, A);

Insert (q, B);

Insert (q, C);

Убираем элемент A из очереди:

Remove (q)

Операция remove (q) может быть в этом случае реализована следующим образом:

Remove (q)

x = q(1)

for i =1 to R-1

q(i) = q(i+1)

next i

R =R-1

return

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

Другой способ предполагает рассматривать массив, который содержит очередь в виде замкнутого кольца. Это означает, что даже в том случае, если последний элемент занят, новое значение может быть размещено сразу же за ним на месте первого элемента, если этот первый элемент пуст.

Предположим, что очередь содержит три элемента - в позициях 3, 4 и 5 пятиэлементного массива. Хотя массив и не заполнен, последний элемент очереди занят.

Если теперь делается попытка поместить в очередь элемент G, то он будет записан в первую позицию массива. Первый элемент очереди есть q(3), за которым следуют элементы q (4), q(5) и q(1).

К сожалению, условие R<F больше не годится для проверки очереди на пустоту.

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

В этом случае, поскольку R содержит индекс последнего элемента очереди, условие F = R подразумевает, что очередь пуста.

Перед началом работы с кольцевой очередью в F и R устанавливается значение последнего индекса массива maxQ, а не 1 и 0.

Поскольку R = F, то очередь изначально пуста.

Основные операции с кольцевой очередью:

1. Вставка элемента q в очередь x
Insert(q,x);

2. Извлечение элемента из очереди x
Remove(q);

3. Проверка очереди на пустоту
Empty(q);

4. Проверка очереди на переполнение
Full(q).

Операция Empty(q)

if F = R

then empty = true

else empty = false

endif

return

 

Операция Remove(q)

empty (q)

if empty = true

then “пусто”

stop

endif

if F = maxQ

then F =1

else F = F+1

endif

x = q(F)

return

Значение F должно быть модифицировано до момента извлечения элемента.

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

Исходное состояние очереди

Поместим в очередь элемент G.

Если произвести следующую вставку, то массив становится целиком заполненным, и попытка произвести еще одну вставку приводит к переполнению. Это регистрируется тем фактом, что F = R, то есть это соотношение как раз и указывает на переполнение. Очевидно, что при такой реализации нет возможности сделать различие между пустой и заполненной очередью.

Одно из решений состоит в том, чтобы пожертвовать одним элементом массива и позволить очереди расти до объема, на единицу меньшего максимального. Предыдущий рисунок иллюстрирует именно это соглашение. Попытка разместить в очереди еще один элемент приведет к переполнению. Проверка на переполнение в функции insert производится после установления нового значения для R, в то время как проверка на потерю значимости в функции remove производится сразу же после входа в подпрограмму до момента обновления значения F.

Функция Insert(q,x) может быть записана следующим образом:

if R = maxQ

then R = 1

else R = R+1

endif

‘проверка на переполнение’

if R = F

then print «переполнение очереди»

stop

endif

q (R) =x

return