К полустатическим структурам данных относят стеки, деки и очереди.
Списки
Это набор связанных элементов данных, которые в общем случае могут быть разного типа.
Пример списка:
E1, E2, ........, En,... n > 1 и не зафиксировано.
Количество элементов списка может меняться в процессе выполнения программы. Различают 2 вида списков:
1) Несвязные
2) Связные
В несвязных списках связь между элементами данных выражена неявно. В связных списках в элемент данных заносится указатель связи с последующим или предыдущим элементом списка.
Стеки, деки и очереди - это несвязные списки. Кроме того они относятся к последовательным спискам, в которых неявная связь отображается их последовательностью.
Стеки
Очередь вида LIFO (Last In First Out - Последним пришел, первым ушел), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним, называется стеком. Это одна из наиболее употребляемых структур данных, которая оказывается весьма удобной при решении различных задач.
В силу указанной дисциплины обслуживания, в стеке доступна единственая его позиция, которая называется вершиной стека - это позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх прежней вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).
Графически стек можно представить следующим образом:
Первый элемент заносится вниз стека. Выборка из стека осуществляется с вершины, поэтому стек является структурой с ограниченным доступом.
Операции, производимые над стеками:
1. Занесение элемента в стек.
Push(S,x), где S - идентификатор стека, x - заносимый элемент.
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
условие i =0 означает, что стек пуст
Full(S)
if i = maxS
then “ переполнение ”
Stop
return
endif
StackTop(S )
x = S ( i )
return
При выполнении операции выборки из стека сначала необходимо осуществить проверку на пустоту стека. Если он пуст, то Empty возвращает значение True. Если Empty возвращает False, то это означает, что стек не пуст и из него еще можно выбирать элементы.
Если при выборке проверять стек на пустоту, а при занесении элемента проверять стек на переполнение, то алгоритмы операций считывания и занесения элемента будут следующими:
Pop(S)
if i = 0 then “ пусто ”
Stop
return
endif
x = S(i)
i = i -1
return
Push(S,i)
if i = maxS
then “ переполнение ”
Stop
return
endif
i = i+1
S ( i ) = x
return
Очередь
Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются заказы на то или иное обслуживание.
В программировании имеется структура данных, которая называется очередью. Эта структура данных используется, например, для моделирования реальных очередей с целью определения их характеристик при данном законе поступления заказов и дисциплине их обслуживания. По своему существу очередь является полустатической структурой- с течением времени и длина очереди, и состав могут изменяться.
На рис. 2. 13 приведена очередь, содержащая четыре элемента — А, В, С и D. Элемент А расположен в начале очереди, а элемент D — в ее конце. Элементы могут удаляться только из начала очереди, то есть первый помещаемый в очередь элемент удаляется первым. По этой причине очередь часто называют списком, организованным по принципу «первый размещенный первым удаляется» в противоположность принципу стековой организации — «последний размещенный первым удаляется».
Дисциплину обслуживания, в которой заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди), называется FIFO (First In First Out - Первым пришел, первым ушел). Очередь открыта с обеих сторон.
Таким образом, изъятие компонент происходит из начала очереди, а запись – в конец. В этом случае вводят два указателя: один - на начало очереди, второй - на ее конец.
Реальная полустатическая очередь создается в памяти ЭВМ в виде одномерного массива с конечным числом элементов, при этом необходимо указать тип элементов очереди, а также необходима переменная в работе с очередью.
Физически очередь занимает сплошную область памяти, и элементы следуют друг за другом, как в последовательном списке.
Операции, производимые над очередью:
Для очереди определены три примитивные операции. Операция insert (q,x) помещает элемент x в конец очереди q. Операция remove(q) удаляет элемент из начала очереди q и присваивает его значение переменной x. Третья операция, empty (q), возвращает значение true или false в зависимости от того, является ли данная очередь пустой или нет. Учитывая то, что полустатическая очередь реализуется на одномерном массиве, необходимо следить за возможностью его переполнения. С этой целью вводится операция full(q).
Операция insert для динамической очереди может быть выполнена всегда, поскольку на количество элементов, которые может содержать очередь, никаких ограничений не накладывается. В полустатической очереди при проведении операции вставки необходимо осуществление проверки на переполнение, поскольку массив, с помощью которого она реализуется, состоит из конечного числа элементов. Операция remove применима только к непустой очереди, поскольку невозможно удалить элемент из очереди, не содержащей элементов. Результатом попытки удалить элемент из пустой очереди является возникновение исключительной ситуации, которая носит название потеря значимости. Операция empty, разумеется, выполнима всегда.
Дата: 2019-12-10, просмотров: 326.
