Очередь

Очередь – это динамическая связанная структура данных, организованная по принципу “ первым пришел, первым ушел ” или, как говорят, реализующая дисциплину обслуживания 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(); /* задержка экрана результатов */

}

Результаты программы: