Лекция: Инициализация очереди
| #define Maxg | ||
| float | git[Maxg]; | |
| f rnt = | = Maxg; | |
| rear = | = Maxg; |
Операция empty
if(frnt == rear) empty=l; else empty =0;
Операция remove
| if | (empty | == 1) | ||
| printf( | «Очередь | пуста») | r | |
| if | (frnt = | = Maxg-1) | frnt = | 0; |
| else frnt | = frnt + | 1; | ||
| remove = g | it[frnt]; |
При реализации вставки необходимо контролировать ситуацию переполнения, при которой frnt = rear. Это же условие характеризует пустую очередь. Одно из решений проблемы — очередь растет до Maxg-\.
Операция insert
/^выделение места для элемента*/ if (rear == Maxg — 1) rear = 0; else rear = rear + 1;
| /^проверка | на переполнение | */ |
| if (rear = | = frnt) | |
| printf( | «Переполнение.» | ); |
| git [rear] | = x; |
Функции, реализующие операции работы с очередью
int empty()
{
if (frnt ==rear) return 1;
else return 0; }
float remove()
{
if(empty() == 1)
{
printf(«Очередь пуста.»); return 0.0;
} else
{
if(frnt == (Maxq-1)) frnt=0; else frnt++; return git[frnt]; } }
void insert(float x)
{
if(rear == (Maxq-1)) rear = 0;
else rear++;
if(rear == frnt)
printf(«Переполнение!»);
else git[rear]=x; }
Реализация очереди на базе однонаправленного связанного списка
Однонаправленный связанный список можно рассматривать в качестве очереди поскольку (рис. 2.12): а) определены начало и конец списка, б) задан порядок расположения узлов.
| info |
ptrn —■*
t
frnt
Начало очереди
info
ptrn
ptrn=NULL —■*! info ptrn
rear
Конец очереди