Очередь - одномерная структура данных, для кот. загрузка или извлечение элементов осущ. с помощью указателей начала извлечения (head) и конца (tail) очереди в соотв. с правилом FIFO (" first-in, first-out " - "первым введен, первым выведен"), т. е. включение производится с одного, а исключение – с другого конца.
| Задание
| Краткие теоретические сведения
|
| 1. В программе, приведенной справа, демонстрируется реализация очереди на основе односвязного списка.
Внести изменения в главную функцию с тем, чтобы выводились различные варианты содержимого очереди.
| | #include <iostream>
using namespace std;
struct Queue
{ int val; Queue *next; };
//Постановка элемента в конец очереди,
void intoFIFO(Queue *ph[], int v)
{ Queue *p= new Queue;
p->val = v; p->next = NULL;// новый элемент - последний
if (ph[0] == NULL)
ph[0] = ph[1] = p; // включение в пустую очередь
else { ph[1]->next = p; ph[1] = p; }
}
void scan(Queue *ph[]) //вывод
{ for(Queue* p=ph[0];p!=NULL;p=p->next)
cout<<p->val<<" ";
cout<<"\n"; }
| int fromFIFO(Queue *ph[])//извлечение
{ Queue *q;
if (ph[0] ==NULL) return -1;// очередь пуста
q = ph[0]; // исключение первого элемента
ph[0] = q->next;
if (ph[0] ==NULL) ph[1] = NULL;//
int v = q->val; return v;
}
void main()
{ Queue A3={7,NULL}, A2={5,&A3}, A1={1,&A2};
Queue* ph[2];
ph[0]=&A1, ph[1]=&A3;
scan(ph); intoFIFO (ph,10);
intoFIFO (ph,2);
scan(ph); int vv= fromFIFO (ph);
scan(ph); }
|
|
| 2. Изучить реализацию очереди на основе списка с пр иоритетным включением, выполнив программу, приведенную в правой части.
| В реальных задачах иногда возникает необходимость в формировании очередей, отличных от FIFO или LIFO. Порядок выборки элементов из таких очередей определяется приоритетами элементов. Приоритет в общем случае может быть представлен числовым значением, которое вычисляется либо на основании значений каких-либо полей элемента, либо на основании внешних факторов. В данном примере каждый элемент при добавлении его в очередь вставляется в нужное место так, чтобы очередь всегда была упорядочена.
| #include<iostream>
using namespace std;
struct item
{ int data;
item *next; };
item *head, *tail;
void delet1()//извлечение эл-та из начала
{ if(isnull())
cout<<"Очередь пуста"<<endl;
else
{ item *p = head;
head = head -> next;
delete p; }
}
void fromhead()//получение эл-та из начала
{ if(isnull())
cout<<"Очередь пуста"<<endl;
else
cout<<"Начало = "<<head -> data <<endl;
}
void add(int x)//добавить эл-т в очередь
{ item *p = new item;//новый указатель
p -> data = x; p -> next = NULL;
item *v = new item;//указатель для нового числа
item *p1 = new item
item *p2 = new item;
int i = 0;// флажок
if (isnull()) head = tail = p;
else
{ p2 = head; p1 = head;
while(p1!= NULL)//пока очередь не закончится
{if (i == 1)
{if(x <= p1 -> data)//число меньше, чем в очереди
{ v -> data = x; v -> next = p1;
p2 -> next = v; return; }
p2 = p2 -> next; }// следующее число
else
{ if(x <= p1 -> data)
{ v -> data = x; v -> next = p1;
head = v; return; } }
p1 = p1 -> next; i = 1; }
if(p1 == NULL)
{ tail -> next = p; tail = p; } }
}
| void out()//вывод очереди
{ item *p = new item;
if(isnull()) cout<<"Очередь пуста"<<endl;
else { cout<<"Очередь = ";
p = head;
while(!isnull())
{ if (p!= NULL)
{
cout<<p->data<<" ";
cout<<"->";
p = p -> next; }
else
{ cout<<"NULL"<<endl;
return; } } }
}
void clrscr()//очистка очереди
{
while(!isnull()) delet1();
}
int main()
{ setlocale (LC_CTYPE, "Russian");
int i = 1, num = 1, z;
head = NULL; tail = NULL;
while (num!= 0)
{cout<<"1 - добавить элемент"<<endl;
cout<<"2 - получить элемент с начала"<<endl;
cout<<"3 - извлечь элемент с начала"<<endl;
cout<<"4 - вывести элементы"<<endl;
cout<<"5 - очистить очередь"<<endl;
cout<<"0 - выход"<<endl;
cout<<"Выберите действие ";
cin>>num;
switch(num)
{case 1: cout<<"Введите элемент: ";
cin>>z; add(z);
out(); break;
case 2: fromhead(); break;
case 3: delet1(); break;
case 4: out(); break;
case 5: clrscr(); break; }
}
return 0;
}
|
|
| 3. Изучить реализацию очереди на основе динамического массива, выполнив программу, приведенную в правой части.
Дописать главную функцию.
| | Главная функция
#include "Common.h"
#include <iostream>
struct str1 { int a; char b; };
struct str2 { char b; long a; };
int main()
{ str1 a1={1, 'q'}; str1 a2={2, 'w'};
str1 a3={3, 'e'}; str2 b1={'a', 1};
str2 b2={'s', 2}; str2 b3={'d', 3};
str2* b4=new str2;
b4->a=4; b4->b='f';
str1* a4=new str1;
a4->a=4; a4->b='r';
queue::Object q1=queue::Create(3);
queue::Insert(q1,&a1);
...................
str1* x=(str1*)queue::Select(q1);
x=(str1*)queue::Delete(q1);
...................
queue::Object q2=queue::Create(q1);
queue::Insert(q1,a4); queue::Clear(q1);
queue::Copy(q1, q2);
queue::Append(q2, q1);
queue::Release(q1);
queue::Release(q2);
return 0; }
Программный модуль MyQueue_1.cpp
#pragma once
#include "MyQueue_1.h"
#include <string.h>
Queue CreateQueue(int n)// выделить ресурс для очереди
{ return *(new Queue(n));};
Queue CreateQueue(const Queue& pq)// создать очередь по образцу
{ Queue *rc = new Queue(pq.Size-1);
rc->Head = pq.Head; rc->Tail = pq.Tail;
for (int i = 0; i < pq.Size; i++)
rc->Data[i] = pq.Data[i]; return *rc;
}
bool Enq(Queue& q, void* x)// добавить x { bool rc = true;
if (rc =!q.isFull())
{q.Data[q.Tail] = x; q.Tail=(q.Tail+1)%q.Size;}
else rc=false;
return rc; };
void* Deq(Queue& q)// удалить элемент
{void* rc = (void*)MYQUEUE1_EQE;
if (!q.isEmpty())
{ rc = q.Data[q.Head];
q.Head=(q.Head+1)%q.Size; }
else rc=NULL;
return rc; }
void* Peek(const Queue& q)
{void* rc = (void*)MYQUEUE1_EQE;
if (!q.isEmpty()) rc = q.Data[q.Head];
else rc=NULL; return rc; }
int ClearQueue(Queue& q)// очистить очередь
{ int rc = (q.Tail - q.Head)>=0?(q.Tail - q.Head):(q.Size-q.Head+q.Tail+1);
q.Tail = q.Head = 0;
return rc;// колич. элементов до очистки
}
void ReleaseQueue(Queue& q)// освободить ресурсы очереди
{ delete[] q.Data;
q.Size = 1; q.Head = q.Tail = 0;}
void AppendQueue(Queue& to, const Queue& from) //добавить одну очередь к другой ()
{ for (int i = from.Head; i!= from.Tail; (++i)%from.Size) Enq(to, from.Data[i]); }
void CopyQueue(Queue& to, const Queue& from) //копировать очередь
{ ClearQueue(to); AppendQueue(to, from); }
void RemoveQueue(Queue& to, Queue& from) //переместить очередь
{ CopyQueue(to, from); ClearQueue(from); }
bool Queue::isFull() const
{return (Head%Size == (Tail+1)%Size);}; //очередь заполненa?
bool Queue::isEmpty()const {return (Head%Size == Tail%Size);};// Очередь пустa?
| Заголовочная функция MyQueue_1.h
#define MYQUEUE1_EQE0x0000 // возврат в случае пустоты очереди
struct Queue// блок управления очередью
{ int Head;// голова очереди
int Tail;// хвост очереди
int Size;// размер очереди (макс. колич.+1)
void** Data;// хранилище данных очереди
Queue(int size)
{ Head = Tail = 0;
Data = new void*[Size = size+1]; }// физический
размер очереди = (макс. количество элементов +1)
bool isFull() const;// очередь заполненa?
bool isEmpty()const;// очередь пустa?
};
Queue CreateQueue(int n);// n – макс. колич.
Queue CreateQueue(const Queue& pq); // создать очередь по образцу
bool Enq(Queue& q, void* x);// добавить x в очередь s
void* Deq(Queue& q); //удалить элемент
void* Peek(const Queue& q);// получить первый элем.
int ClearQueue(Queue& q); //очистить очередь
void ReleaseQueue(Queue& q); /освободить ресурсы
void AppendQueue(Queue& to, const Queue& from); // //добавить одну очередь к другой
void CopyQueue(Queue& to, const Queue& from); // //копировать очередь
void RemoveQueue(Queue& to, Queue& from); // //переместить очередь
Заголовочная функция Common.h
#pragma once
#include "MyQueue_1.h"
//-- обобщенные интерфейсы
namespace queue// интерфейс очереди
{ typedef Queue Object;// новое имя блока управления
const void* Empty = MYQUEUE1_EQE; //возврат в случае пустоты очереди
Object Create(int n)
{ return CreateQueue(n);
}; //выделить ресурса для очереди
Object Create(Object& o)
{ return CreateQueue(o);
}; //создать очередь по образцу
bool Insert(Object& o, void* x)
{ return Enq(o, x);
}; //добавить x в очередь s
void* Delete(Object& o)
{ return Deq(o);
}; //удалить элемент из очереди
void* Select(const Object& o)
{ return Peek(o);
}; //получить первый элемент очереди
void Release(Object& o)
{ ReleaseQueue(o);
}; //освободить ресурсы очереди
bool isFull(const Object& o)
{ return o.isFull();
}; //очередь заполнена?
bool isEmpty(const Object& o)
{ return o.isEmpty();
};// очередь пуста?
int Clear(Object& o)
{ return ClearQueue(o);
}; //очистить очередь
void Append(Object& to, const Object from)
{ AppendQueue(to,from);
}; //добавить одну очередь к другой
void Copy(Object& to, const Object from)
{ CopyQueue(to, from);
};
}
|
|
4. Создать проект, демонстрирующий работу с очередью. В соответствии со своим вариантом выполнить задание из таблицы, представленной ниже. Для организации очереди использовать структуру с функциями и реализовать все операции с очередью через функции. Объявления записать в заголовочном файле проекта, определение функций и реализацию алгоритма выполнить в отдельных модулях.
| № варианта
| Задание для выполнения
|
| 1, 8
| Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие - подряд из младших адресов (начало очереди). Приоритет: мin значение числового параметра, при совпадении параметров - LIFO.
|
| 2, 4
| Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие - подряд из младших адресов (начало очереди). Приоритет: мах значения числового параметра, при совпадении параметров - FIFO
|
| 5, 3
| Разработать функцию, которая по одной очереди строит две новых: Queue1 из положительных элементов и Queue2 - из остальных элементов очереди.
|
| 6, 7
| Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие - подряд из старших адресов (конец очереди). Приоритет: мin значение числового параметра, при совпадении параметров - LIFO.
|
| 9, 12
| Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие - подряд из старших адресов (конец очереди). Приоритет: мin значение числового параметра, при совпадении параметров - LIFO
|
| 10, 11
| Разработать функцию, которая в очереди переставляет в обратном порядке все элементы между первыми последним вхождением элемента E, если E входит в L не менее двух раз
|
| 13, 16
| Разработать функцию, которая по одной очереди строит две новых: Queue1 из положительных элементов и Queue2 - из остальных элементов очереди.
|
| 14, 15
| Разработать функцию, которая удаляет из очереди первый отрицательный элемент, если такой есть.
|
В начало практикума
