Очередь – это динамическая связанная структура данных, организованная по принципу “ первым пришел, первым ушел ” или, как говорят, реализующая дисциплину обслуживания FIFO (First In, First Out). Начало очереди может храниться, например, в переменной с именем head (голова очереди). Базовыми операциями для работы с очередью являются:
· добавление нового элемента в конец очереди;
· удаление элемента из начала очереди.
Пример. Демонстрация работы с очередью. В программе начало очереди представлено в виде переменной-указателя на указатель (**head), поскольку адрес начала очереди может динамически изменяться. При удалении первого элемента адресом начала очереди становится адрес второго элемента и т.д.
Используются следующие функции для работы с очередью:
· INSERT () – выделяет память под очередной элемент, заносит в него информацию и ставит в конец очереди.
· TAKE_OFF () – удаляет из очереди ее первый элемент, освобождает занимаемую им память и перемещает указатель начала очереди на следующий элемент. При попытке удалить элемент из пустой очереди в параметр ошибки error заносится 1.
· OUT_ELEMENTS () – выводит на экран информацию элемента очереди.
Программа:
#include<stdio.h>
#include<alloc.h> /* функции динамического распределения памяти */
#include<conio.h>
#define QUEUE struct queue /* новое имя шаблона структуры */
QUEUE { /* шаблон элемента очереди */
int info; /* поле информации элемента очереди */
QUEUE *next; /* поле ссылки на следующий элемент очереди */
};
/* Функция включения элемента в очередь: */
void INSERT (QUEUE **head, int item)
{ QUEUE *tek = *head, /* установка текущего указателя на начало */
*pred = NULL, /* обнуление указателя на следующий элемент */
*new; /* указатель на новый элемент */
while (tek) /* цикл просмотра очереди до конца */
{ pred = tek; /* сдвиг указателя предыдущего элемента */
tek = tek->next; /* сдвиг текущего указателя к следующему */
}
new = (QUEUE*)malloc(sizeof(QUEUE)); /* место для нового элемента */
new->info = item; /* заполнение поля информации элемента */
if (pred) /* если очередь не пуста */
{ new->next = NULL; /* за новым элементом ничего нет */
pred->next = new; /* новый элемент включен в очередь */
}
else /* если очередь пуста */
{ *head = new; /* новый элемент во главе очереди */
new->next = NULL; /* за новым элементом ничего нет */
}
}
/* Функция удаления элемента из очереди: */
int TAKE_OFF (QUEUE **head, int *error)
{ int value = 0; /* возвращаемое значение функции */
QUEUE *old = *head; /* указатель на “старую” голову очереди */
if (*head) /* если очередь не пуста */
{ value = old ->info; /* информация для возвращаемого значения */
*head = old ->next; /* во главе очереди следующий элемент */
free (old); /* удаление первого элемента из очереди */
*error = 0; /* отсутствие ошибки удаления */
}
else *error = 1; /* ошибка удаления из пустой очереди */
return value; /* возвращение значения функции */
}
/* Функция вывода элементов очереди: */
void OUT_ELEMENTS (QUEUE **head)
{ QUEUE *tek = *head; /* текущий указатель в начале очереди */
if (!tek) /* если очередь пустая, то сообщение */
puts ("Очередь пустая.");
else /* если очередь не пустая */
{ while (tek) /* цикл пока есть очередной элемент */
{ printf("Элемент %d\n", tek->info); /* вывод информации об элементе */
tek = tek->next; /* переход к следующему элементу */
}
}
}
void main() /* главная функция */
{ int error, i; /* переменные ошибки и цикла */
QUEUE *q1=NULL, *q2=NULL; /* инициализация указателей на очереди */
clrscr(); /* очистка экрана */
puts ("Заполнение первой очереди.");
for (i=12; i<=14; i++) /* цикл заполнения первой очереди */
INSERT (&q1, i); /* включение в очередь элемента */
puts ("Первая очередь:");
OUT_ELEMENTS (&q1); /* вывод элементов очереди */
puts ("Вторая очередь:");
OUT_ELEMENTS (&q2); /* вывод элементов очереди */
puts ("\nЗаполнение второй очереди.");
while (q1) /* цикл пока не пуста 1-я очередь */
INSERT(&q2, TAKE_OFF(&q1, &error)); /* перенос эл-та из1-й во 2-ю очередь */
puts ("Первая очередь:");
OUT_ELEMENTS (&q1); /* вывод элементов очереди */
puts ("Вторая очередь:");
OUT_ELEMENTS (&q2); /* вывод элементов очереди */
puts ("\nУдаление элементов из второй очереди");
while (q2) /* цикл пока не пуста 2-я очередь */
printf ("Удален из q2: %d\n", TAKE_OFF(&q2, &error));
puts ("Вторая очередь:");
OUT_ELEMENTS (&q2); /* вывод элементов очереди */
getch(); /* задержка экрана результатов */
}
Результаты программы: