Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

StackTop(S)

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

type
Stack = Array[1..10] of Integer; {стек вместимостью 10 элементов типа Integer}

var
StackCount: Integer; {Переменная — указатель на вершину стека, ее начальное   значение должно быть равно 0}
S: Stack; {Объявление стека}

Procedure Push(I: Integer; var S: Stack);
begin
Inc(StackCount);
S[StackCount]:=I;
end;

Procedure Pop(var I: Integer; S: Stack);
begin
I:=S[StackCount];
Dec(StackCount);
end;

Function Empty: Boolean;
begin
If  I = 0 then Empty:=True Else Empty:=False;
end;

При выполнении операции выборки из стека сначала необходимо осуществить проверку на пустоту стека. Если он пуст, то Empty возвращает значение True. Если Empty возвращает False, то это означает, что стек не пуст и из него еще можно выбирать элементы.

Procedure StackTop(var I: Integer; S: Stack);
begin
I:=S[StackCount];
end;

2.4.2  Очередь
Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются заказы на то или иное обслуживание.
В программировании имеется структура данных, которая называется очередью. Эта структура данных используется, например, для моделирования реальных очередей с целью определения их характеристик при данном законе поступления заказов и дисциплине их обслуживания. По своему существу очередь является полустатической структурой- с течением времени и длина очереди, и состав могут изменяться.
На рис. 2. 13  приведена  очередь,  содержащая четыре элемента — А, В, С и D. Элемент А расположен в начале очереди, а элемент D — в ее конце. Элементы могут удаляться только из начала очереди, то есть первый помещаемый в очередь элемент удаляется первым. По этой причине очередь часто называют списком, организованным по принципу «первый размещенный первым удаляется» в противоположность принципу стековой организации — «последний размещенный первым удаляется».
Дисциплину обслуживания, в которой заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди), называется FIFO (First In First Out — Первым пришел, первым ушел). Очередь открыта с обеих сторон.
Таким образом, изъятие компонент происходит из начала очереди, а запись- в конец. В этом случае вводят два указателя: один — на начало очереди, второй- на ее конец.
Реальная очередь создается в памяти ЭВМ в виде одномерного массива с конечным числом элементов, при этом необходимо указать тип элементов очереди, а также необходима переменная в работе с очередью.

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

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

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники