Представление очереди в виде списка
Можно хранить очередь в виде списка с указателями начала и конца. Операции реализуются методами обработки списков (раздел 2). Чтобы не программировать отдельным вариантом случай включения элемента в пустую очередь, можно хранить указатель начала не в виде скалярной переменной, а в поле ссылки специального фиктивного элемента в начале списка (его поле информации не используется). У пустой очереди указатель конца ссылается на этот фиктивный элемент (рис. 3.4). Можно использовать кольцевой список.
Рис. 3.4. Очередь в виде списка с фиктивным элементом
Представление в виде списка удобно для элементов переменного размера, очереди трудно предсказуемого размера и для очереди с приоритетами.
В очереди с приоритетами исключение элементов происходит не в порядке поступления, а по приоритету (старшинству). Для этого элементы упорядочиваются в очереди по убыванию приоритета (т.е. включаются не обязательно в конец), что удобно делать в списке. Более эффективна реализация с помощью адресной арифметики, приведенная в разделе 3.3.3 (пример 3.23).
Рассмотрим описание данных и алгоритмы типовых операций для представления очереди списком, как на рис. 3.4.
Пример 3.5. Описание данных для представления очереди в виде списка:
struct el_och /* Тип элемента списка */
{ Тип-элемента inf; /* Информация */
struct el_och *sled; /* Ссылка на следующий элемент */
};
struct el_och f; /* Фиктивный начальный элемент */
struct el_och *uk; /* Указатель конца очереди */
Пример 3.6. Инициализация (создание) пустой очереди:
f.sled = NULL; /* Указатель начала очереди */
uk = &f; /* Указатель конца очереди */
Пример 3.7. Исключение из очереди элемента и присваивание его переменной x (обозначим эту операцию Очередь ==> x):
Тип-элемента x; /* Значение исключенного элемента */
struct el_och *i; /* Указатель исключенного элемента */
...
if (f.sled!= NULL) /* В очереди есть элементы */
{ x = f.sled->inf; /* Запоминание значения */
i = f.sled;
f.sled = f.sled->sled; /* Исключение элемента */
free (i); /* Освобождение памяти */
if (f.sled == NULL) uk = &f; /* Очередь стала пустой */
}
else... /* Очередь пуста */
Пример 3.8. Включение в очередь элемента равного x (обозначим эту операцию Очередь <== x):
Тип-элемента x; /* Включаемое значение */
struct el_och *i; /* Указатель включаемого элемента */
...
i = malloc (sizeof(struct el_och)); /* Получение памяти */
if (i!= NULL) /* Есть место */
{ i->inf = x; /* Запись информации */
i->sled = NULL; /* Запись ссылки */
uk.sled = i; /* Соединить *i с концом очереди */
uk = i; /* Новый указатель конца */
} else... /* Переполнение очереди */
Стек
Стек (stack) - это упорядоченная последовательность элементов, в которой выполняются операции включения и исключения элемента по принципу LIFO (Last-In-First-Out) - "последним пришел - первым ушел", т. е. включение и исключение всегда происходят в одном конце (рис. 3.5). Этот конец называют верхом, противоположный - дном стека. Другие названия стека: магазин (по аналогии с магазином пистолета или автомата), очередь типа LIFO.
S[1]
|
S[2]
|
…
|
S[k]
|
|
| ¾¾¾®
¾¾¾
|
Дно
|
|
|
Верх
|
|
| Включение и
исключение
элементов
| Рис. 3.5. Стек
Примеры стека: заднее сиденье легкового автомобиля, когда посадка и высадка происходит с одной стороны; стопка подносов в столовой, где подносы берутся и кладутся только сверху.
Назовем некоторые из многочисленных применений стека.
1. Переупорядочивание данных для обработки в порядке, отличающемся от порядка поступления.
2. Запоминание подзадач некоторой задачи с последующим решением подзадач в порядке, обратном порядку их возникновения (см. алгоритм обхода дерева в глубину).
3. Области локальных данных (включая параметры и адреса возврата) вложенных вызовов подпрограмм.
4. Области локальных данных вложенных блоков программы.
5. Трансляция скобочных структур: выражений, вложенных ветвлений, циклов, блоков и всей программы (см. раздел 7).
6. ЭВМ и микрокалькуляторы с безадресной магазинной памятью.
7. Стек в мозге человека (7 ± 2 элемента). Психологи обнаружили, что человек может воспринимать именно такую глубину вложенности, например, придаточных предложений фразы или такое количество рассматриваемых вместе дел, понятий и т. п.
Типовые операции над стеком:
1. Инициализация (создание, подготовка к работе);
2. Вталкивание (включение) элемента - PUSH;
3. Выталкивание (исключение) элемента - POP;
4. Проверка пустоты стека;
5. Проверка переполнения стека;
6. Доступ к вершине (получение / изменение значения последнего поступившего элемента).
Дата добавления: 2015-09-27 | Просмотры: 470 | Нарушение авторских прав
|