2015-02-27
2391
Данный способ позволяет организовать и впоследствии обрабатывать очередь, имеющую фиксированный размер. Определим список операций, который будет использоваться как при реализации статической очереди, так и динамической:
· Creation (Q) – создание очереди Q;
· Full (Q) – проверка очереди Q на пустоту;
· Add (Q) – добавление элемента в очередь Q (его значение задается из функции);
· Delete (Q) – удаление элемента из очереди Q;
· Top (Q) – вывод начального элемента очереди Q;
· Size (Q) – размер очереди Q.
В программе каждая из этих операций предстанет в виде отдельной подпрограммы. Помимо того, потребуется описать массив данных data [ n ], по сути, являющийся хранилищем данных вместимостью n, а также указатель на конец очереди (на ту позицию, в которую будет добавлен очередной элемент) – last. Изначально last равен 0.
const int n=4; //размер очереди
struct Queue
{
int data[n]; //массив данных
int last; //указатель на начало
};
void Creation(Queue *Q) //создание очереди
{ Q->last=0; }
bool Full(Queue *Q) //проверка очереди на пустоту
{
if (Q->last==0) return true;
|
|
|
else return false;
}
void Add(Queue *Q) //добавление элемента
{
if (Q->last==n)
{ cout<<"\nОчередь заполнена\n\n"; return; }
int value;
cout<<"\nЗначение > "; cin>>value;
Q->data[Q->last++]=value;
cout<<endl<<"Элемент добавлен в очередь\n\n";
}
void Delete(Queue *Q) //удаление элемента
{
for (int i=0; i<Q->last && i<n; i++) //смещение элементов
Q->data[i]=Q->data[i+1]; Q->last--;
}
int Top(Queue *Q) //вывод начального элемента
{ return Q->data[0]; }
int Size(Queue *Q) //размер очереди
{ return Q->last; }
void main() //главная функция
{
Queue Q;
Creation(&Q);
char number;
do
{
cout<<"1. Добавить элемент"<<endl;
cout<<"2. Удалить элемент"<<endl;
cout<<"3. Вывести верхний элемент"<<endl;
cout<<"4. Узнать размер очереди"<<endl;
cout<<"0. Выйти\n\n";
cout<<"Номер команды > "; cin>>number;
switch (number)
{
case '1': Add(&Q);
break;
case '2':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else
{
Delete(&Q);
cout<<endl<<"Элемент удален\n\n";
}
break;
case '3':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else cout<<"\nНачальный элемент: "<<Top(&Q)<<"\n\n";
break;
case '4':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else cout<<"\nРазмер очереди: "<<Size(&Q)<<"\n\n";
break;
case '0': break;
default: cout<<endl<<"Команда не определена\n\n";
break;
}
} while(number!='0');
}
В функции main, сразу после запуска программы, создается переменная Q структурного типа Queue, адрес которой будет посылаться в функцию (в зависимости от выбора операции) как фактический параметр. Функция Creation создает очередь, обнуляя указатель на последний элемент. Далее выполняется оператор цикла do..while (цикл с постусловием), выход из которого осуществляется только в том случае, если пользователь ввел 0 в качестве номера команды. В остальных случаях вызывается подпрограмма соответствующая команде, либо выводиться сообщение о том, что команда не определена.
|
|
|
Из всех подпрограмм особого внимания заслуживает функция Delete. Удаление элемента из очереди осуществляется путем сдвига всех элементов в начало, т. е. значения элементов переписываются: в data [0] записывается значение элемента data [1], в data [1] – data [2] и т. д.; указатель конца смещается на позицию назад. Получается, что эта операция требует линейного времени O (n), где n – размер очереди, в то время как остальные операции выполняются за константное время. Данная проблема поддается решению. Вместо «мигрирующей» очереди, наиболее приемлемо реализовать очередь на базе циклического массива. Здесь напрашивается аналогия с очередью в магазин: если в первом случае покупатели подходили к продавцу, то теперь продавец будет подходить к покупателям (конечно, такая тактика оказалась бы бесполезной, например, в супермаркетах и т. п.). В приведенной реализации очередь считалась заполненной тогда, когда указатель last находился над последней ячейкой, т. е. на расстоянии n элементов от начала. В циклическом варианте расширяется интерпретация определения позиции last относительно начала очереди. Пусть на начало указывает переменная first. Представим массив в виде круга – замкнутой структуры. После последнего элемента идет первый, и поэтому можно говорить, что очередь заполнила весь массив, тогда когда ячейки с указателями last и first находятся радом, а именно за last следует first. Теперь, удаление элемента из очереди осуществляется простым смещением указателя first на одну позицию вправо (по часовой); чтобы добавить элемент нужно записать его значение в ячейку last массива data и сместить указатель last на одну позицию правее. Чтобы не выйти за границы массива воспользуемся следующим выражением:
(A mod n) + 1
Здесь A – один из указателей, n – размер массива, а mod – операция взятия остатка от деления.
В циклической реализации, как и прежде, очередь не содержит элементов тогда, когда first и last указывают на одну и ту же ячейку. Но в таком случае возникает одно небольшое отличие этой реализации от предшествующей. Рассмотрим случай заполнения очереди, основанной на базе массива, размер которого 5:
| Элементы | first | last |
| - | ||
| 1, 2 | ||
| 1, 2, 3 | ||
| 1, 2, 3, 4 |
В левом столбце записаны произвольные значения элементов, а в двух других значения указателей при соответствующем состоянии очереди. Необходимо заметить, что в массив размером 5 удалось поместить только 4 элемента. Все дело в том, что еще один элемент требует смещения указателя last на позицию 1. Тогда last = first. Но именно эта ситуация является необходимым и достаточным условием отсутствия в очереди элементов. Следовательно, мы не можем хранить в массиве больше n -1 элементов.
В следующей программе реализован интерфейс очереди, основанной на базе циклического массива:
const int n=6; //размер очереди
struct Queue
{
int data[n]; //массив данных
int first; //указатель на начало
int last; //указатель на конец
};
void Creation(Queue *Q) //создание очереди
{ Q->first=Q->last=1; }
bool Full(Queue *Q) //проверка очереди на пустоту
{
if (Q->last==Q->first) return true;
else return false;
}
void Add(Queue *Q) //добавление элемента
{
int value;
cout<<"\nЗначение > "; cin>>value;
if ((Q->last%(n-1))+1==Q->first)
cout<<"\nОчередь заполнена\n\n";
else
{
Q->data[Q->last]=value;
Q->last=(Q->last%(n-1))+1;
cout<<endl<<"Элемент добавлен в очередь\n\n";
}
}
void Delete(Queue *Q) //удаление элемента
{
Q->first=(Q->first%(n-1))+1;
cout<<endl<<"Элемент удален из очереди\n\n";
}
int Top(Queue *Q) //вывод начального элемента
{ return Q->data[Q->first]; }
int Size(Queue *Q) //размер очереди
|
|
|
{
if (Q->first>Q->last) return (n-1)-(Q->first-Q->last);
else return Q->last-Q->first;
}
void main() //главная функция
{
Queue Q;
Creation(&Q);
char number;
do
{
cout<<"1. Добавить элемент"<<endl;
cout<<"2. Удалить элемент"<<endl;
cout<<"3. Вывести верхний элемент"<<endl;
cout<<"4. Узнать размер очереди"<<endl;
cout<<"0. Выйти\n\n";
cout<<"Номер команды > "; cin>>number;
switch (number)
{
case '1': Add(&Q);
break;
case '2':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else Delete(&Q);
break;
case '3':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else cout<<"\nНачальный элемент: "<<Top(&Q)<<"\n\n";
break;
case '4':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else cout<<"\nРазмер очереди: "<<Size(&Q)<<"\n\n";
break;
case '0': break;
default: cout<<endl<<"Команда не определена\n\n";
break;
}
} while(number!='0');
}
Таким образом, циклический вариант позволяет оптимизировать операцию Delete, которая прежде требовала линейного времени, а теперь выполняется за константное, независимо от длины очереди. Тем не менее, реализация очереди на базе массива имеет один существенный недостаток: размер очереди статичен, поскольку зависит от размера массива. Реализация очереди на базе связного списка позволит обойти эту проблему.
