Операции над очередями
Для реализации операций над очередями будем использовать следующие функции:
добавление элемента в очередь
voidAdd(intLast,intNumber)
проверка пустоты очереди
void Empty (int Start, int Last)
удаление элемента из очереди
voidRemove(intStart,intLast)
Для моделирования очереди будем использовать массив Queue (очередь).
Добавление элемента в очередь
Пусть размер очереди равен maxqueue. Тогда функция добавления элемента в очередь будет выглядеть так:
void Add (int Last, int number)
{
if (Last = =maxqueue) exit(l); // Очередь полна
Queue[Last]=number; // Добавляет элементnumberв очередь
Last++; // Сдвигает указательLastна один элемент вправо
}
Функция exit прекращает вызываемый процесс. Перед выходом из процесса все файлы закрываются, записывается буферный вывод (ждущий вывода) и вызываются зарегистрированные "функции выхода".
Проверка очереди на наличие элементов
Данная функция возвращает р=1, если очередь пуста, и р=2, если в очереди есть элементы.
void Empty (int Start, int Last)
if (Start = =Last) p=l; // Очередь пуста
elsep=2; // Очередь не пуста
}
Удаление элемента из очереди
Функция удаления элемента из очереди такова:
void Remove (int Start, int Last) {
if (Start==Last) exit(l); // Очередь пуста
Start++; // Сдвигает указательStartна один элемент вправо
}
Стек
Стеком называется структура данных, элементы которой организованы таким образом, что их удаление будет осуществляться противоположно тому порядку, в котором производилось добавление.
Примером стека может служить стог сена, стопка бумаг на столе, стопка тарелок и т.п. Отсюда произошло название стека, что по-английски означает стопка. Тарелки снимаются со стопки в порядке, обратном их добавлению. Доступна только верхняя тарелка, т.е. тарелка на вершине стека.
Стек применяется довольно часто, причем в самых разных ситуациях. Объединяет их следующая цель: нужно сохранить некоторую работу, которая еще не выполнена до конца, при необходимости переключения на другую задачу. Стек используется для временного сохранения состояния, не выполненного до конца задания. После сохранения состояния компьютер переключается на другую задачу. По окончании ее выполнения состояние отложенного задания восстанавливается из стека, и компьютер продолжает прерванную работу.
Почему именно стек используется для сохранения состояния прерванного задания? Предположим, что компьютер выполняет задачу A. В процессе ее выполнения возникает необходимость выполнить задачу B. Состояние задачи A запоминается, и компьютер переходит к выполнению задачи B. Но ведь и при выполнении задачи B компьютер может переключиться на другую задачу C, и нужно будет сохранить состояние задачи B, прежде чем перейти к C. Позже, по окончании C будет сначала восстановлено состояние задачи B, затем, по окончании B, — состояние задачи A. Таким образом, восстановление происходит в порядке, обратном сохранению, что соответствует дисциплине работы стека.
Стек можно представить в виде вертикального массива с одним указателем на верхний элемент, традиционно называемый вершиной стека (тор). В текущий момент времени вершина стека является доступной. Новый элемент можно добавлять в вершину стека, он же первый подлежит обработке. Стек часто обозначают аббревиатурой LIFO (Last In, First Out — последний зашел, первый вышел).
Элементы стека хранятся в массиве следующим образом: элемент на дне стека располагается в начале массива, т.е. в ячейке с индексом 0. Элемент, расположенный над самым нижним элементом стека, хранится в ячейке с индексом 1, и так далее. Вершина стека хранится где-то в середине массива. Индекс элемента на вершине стека хранится в специальной переменной, которую обычно называют указателем стека (по-английски Stack Pointer или просто SP).
Если стек содержит только один элемент, и этот элемент удаляется, то в результате выполнения операции в данный стек больше не сможет быть занесен ни один элемент. Такой стек называется пустым.
Допустим, имеется стек из элементов А, В и С. Если элемент А был первым занесен в стек, а элемент С — последним, то стек будет выглядеть так, как показано на рис. 1.
Если удалить из стека элемент с, доступный для операций, переместив указатель тор на один элемент вниз, то стек будет выглядеть, как показано на рис. 2.
Теперь добавим в стек некоторый элемент D. Для этого запишем его в вершину стека, сместив указатель тор на один элемент вниз (рис. 3).
1.Содержимое стека 2.Удаление элемента из стека
3.Добавление элемента в стек