Въведение
Опашката е колекция от елементи, където първият елемент, добавен в списъка, трябва да бъде първият елемент, който следва да бъде премахнат. Тъй като артикулите се добавят към колекцията, тя нараства по размер, тоест нараства по дължина. Когато всеки елемент трябва да бъде премахнат, той трябва да бъде първият добавен. Ако елементите се премахват непрекъснато, следващият е премахнат, е вторият елемент; третият се премахва след това и т.н.
След като първият елемент от първоначалния списък е премахнат, вторият става първи елемент. След като вторият елемент е премахнат, третият става първи елемент и т.н.
Добър пример от опашката в реалния живот е, когато хората се наредят, за да изчакат услуга или добро. Първото лице се обслужва първо преди последното. Опашката, за която се говори в този урок, е софтуерната опашка, както е проектирана в C ++.
FIFO
FIFO означава First-In, First-Out. Това е друг начин да оцените опашката. Това означава, че първият елемент, който влиза в списъка, е първият елемент, който трябва да бъде премахнат, винаги когато трябва да се извърши премахването. Началото на списъка се нарича главата или предната част; краят на списъка се нарича гръб или опашка.
Основни операции
Софтуерната опашка трябва да има поне следните операции:
бутане
Тази операция добавя нов елемент в задната част на опашката. Тази операция се нарича официално, enqueue.
смяна
Тази операция премахва първия елемент от опашката, а вторият елемент става новият първи елемент. Тази операция се нарича официално dequeue. Нарича се поп в C ++.
Тази статия обяснява как да използвате структурата от данни на опашката C ++. Трябва да знаете C ++ указатели и препратки, за да разберете останалата част от тази статия.
Клас и обекти
Класът е набор от променливи и функции, които работят заедно, където променливите нямат присвоени стойности. Когато стойностите са присвоени на променливите, класът се превръща в обект. Различни стойности, дадени на един и същи клас, водят до различни обекти; тоест различните обекти са един и същи клас с различни стойности. Създаването на обект от клас се казва за създаване на обект.
Името, опашката, е клас. Обект, създаден от класа на опашката, има име, избрано от програмист.
Функция, която принадлежи към клас, е необходима за създаване на обект от класа. В C ++ тази функция има същото име като името на класа. Обектите, създадени (създадени) от класа, имат различни имена, дадени им от програмиста.
Създаване на обект от класа означава конструиране на обекта; това също означава създаване на екземпляр.
Програма на C ++, която използва класа на опашката, започва със следните редове в горната част на файла:
#включва#включва
използвайки пространство за имена std;
Първият ред е за вход/изход. Вторият ред е да позволи на програмата да използва всички функции на класа на опашката. Третият ред позволява на програмата да използва имената в стандартното пространство от имена.
Претоварване на функция
Когато два или повече различни подписи на функции имат едно и също име, това име се казва претоварено. Когато се извика една функция, броят и видът на аргументите определят коя функция действително се изпълнява.
Строителство
опашка<Тип>име()Следващата декларация създава опашка с име, que от тип int.
опашка<int>че;Опашката е празна. Декларацията започва с запазената дума, опашката, последвана от ъглови скоби с типа данни. След това имате име на програмиста за опашката.
Изграждане със списък на инициализатори
Следващото определение показва как да създадете опашка със списък на инициализатори:
опашка<плувам>че({1.1, 2.2, 3.3, 4.4});Унищожаване на опашка
За да унищожите опашка, просто я оставете да излезе извън обхвата.
Достъп до елемент на опашката
push (стойност)
Опашката е списък First-In-First-Out. Така че всяка стойност се добавя отзад. Следният кодов сегмент създава празна опашка, след което от задната страна се добавят пет плаващи стойности:
опашка<плувам>че;че.бутане(1.1);
че.бутане(2.2);
че.бутане(3.3);
че.бутане(4.4);
че.бутане(5.5);
размер () const
Това връща броя на елементите в опашката. Следният код илюстрира:
опашка<плувам>че;че.бутане(1.1);че.бутане(2.2);че.бутане(3.3);че.бутане(4.4);че.бутане(5.5);
цена<<че.размер() << 'н';
Изходът е 5.
отпред ()
Това връща препратка към първия елемент от опашката, без да се премахва елементът. Изходът на следния код е 1.1.
опашка<плувам>че;че.бутане(1.1);че.бутане(2.2);че.бутане(3.3);че.бутане(4.4);че.бутане(5.5);
цена<<че.отпред() << 'н';
Елементът не се премахва от опашката.
front () const
Когато конструкцията на опашката е предшествана от const, изразът front () const се изпълнява вместо front (). Използва се например в следния код.
constопашка<плувам>че({1.1, 2.2, 3.3, 4.4, 5.5});цена<<че.отпред() << 'н';
Връща се постоянна справка. Елементът не се премахва от вектора. Елементите на опашката не могат да се променят.
обратно()
Това връща препратка към последния елемент от опашката, без да се премахва елементът. Изходът на следния код е 5.5.
опашка<плувам>че;че.бутане(1.1);че.бутане(2.2);че.бутане(3.3);че.бутане(4.4);че.бутане(5.5);
цена<<че.обратно() << 'н';
back () const
Когато конструкцията на опашката е предшествана от const, изразът back () const се изпълнява вместо back (). Използва се например в следния код.
constопашка<плувам>че({1.1, 2.2, 3.3, 4.4, 5.5});цена<<че.обратно() << 'н';
Връща се постоянна справка. Елементът не се премахва от опашката. С предишния const за изграждането на опашката елементите в опашката не могат да се променят.
Капацитет на опашката
размер () const
- виж по-горе
празен () const
Това връща 1 за true, ако няма елементи в опашката, или 0 за false, ако опашката е празна. Следният код илюстрира това:
опашка<плувам>че 1({1.1, 2.2, 3.3, 4.4, 5.5});цена<<че 1.празна() << 'н';
опашка<плувам>това2;
цена<<това2.празна() << 'н';
Изходът е:
01
Модификатори на опашката
поп ()
Опашката е FIFO, така че всеки елемент, който трябва да бъде премахнат, трябва да бъде премахнат от горната част (главата) на опашката. Тази функция член премахва първия елемент, без да го връща. Следният код илюстрира това:
опашка<плувам>че({1.1, 2.2, 3.3, 4.4, 5.5});цена<<че.отпред() << 'н';
че.поп();
цена<<че.размер() << 'н';
Изходът е:
1.14
a.swap (b)
Две опашки могат да бъдат разменени, както е показано в този кодов сегмент:
опашка<плувам>че 1({1.1, 2.2, 3.3, 4.4, 5.5});опашка<плувам>това2({10, двайсет});
че 1.размяна(това2);
цена<< „Първи елемент и размер на que1:
'<<че 1.отпред() <<','<<че 1.размер() << 'н';
цена<< „Първи елемент и размер на que2“<<
това2.отпред() <<','<<това2.размер() << 'н';
Изходът е:
Първи елемент и размер на que1: 10, 2
Първи елемент и размер на que2: 1.1, 5
Имайте предвид, че дължината на опашката се увеличава, ако е необходимо. Също така стойностите, които не са заменени, се заменят с някаква стойност по подразбиране. Типовете данни трябва да са от същия тип.
Оператори за равенство и релационни отношения за опашки
За обикновените знаци в C ++, във възходящ ред, цифрите идват преди главни букви, които идват преди малки букви. Пробелът е преди нулата и всички те.
Оператори на равенство
Връща 1 за true и 0 за false.
Операторът ==
Връща 1, ако двете опашки имат еднакъв размер и съответните елементи са равни; в противен случай връща 0. Пример:
опашка<const char*>че 1({'мил', 'нещо друго'});опашка<const char*>това2({„зъл“});
intникой=че 1==това2;
цена<<никой<< 'н';
Изходът е: 0.
Операторът! =
- обратното на горното. Пример:
опашка<const char*>че 1({'мил', 'нещо друго'});опашка<const char*>това2({„зъл“});
intникой=че 1! =това2;
цена<<никой<< 'н';
Изходът е: 1.
Релационни оператори
Връща 1 за true и 0 за false.
The
Връща 1, ако първата опашка е първоначалното подмножество на втората опашка, като елементите на двете равни части са еднакви и в същия ред. Ако и двете опашки са с еднакъв размер или различни размери и се движат отляво надясно, в първата опашка се среща елемент, който е по -малък от съответния елемент във втората опашка, тогава 1 все пак ще бъде върната. В противен случай се връща 0. Пример:
опашка<const char*>че 1({'мил', 'нещо друго'});опашка<const char*>това2({„зъл“});
intникой=че 1<това2;
цена<<никой<< 'н';
Изходът е 1. > Операторът - обратното на горното. Пример: Изход: 0 The<= Operator - същото като Изход: 1 Операторът> = - обратното на горното. Пример: Изход: 0 Стойността е за тип данни, както създаденият обект е за клас. Конструкцията на опашката също може да приеме клас като тип данни. Следната програма илюстрира това: Изходът е 5. Списъкът с опашки технически се нарича свързан списък. Има два вида свързани списъци за опашката: единично свързан списък и двойно свързан списък. Единично свързан елемент от списък може да бъде реализиран чрез структура от два члена. Единият член държи указател към следващия елемент, а другият член държи референтната точка (единствено число за данни). Двойно свързан елемент на списък може да бъде реализиран чрез структура от три члена. Средният елемент държи референтната точка, докато първият и третият елемент държат указатели към съседните им елементи. Опашката е структура от данни първи в първи излиза. Има ситуации при изчисляването, когато данните пристигат под формата на опашка, което налага поведение първи в първи излиза. Ресурс в компютър е всеки физически или виртуален компонент с ограничена наличност. Те включват процесора, видеокартата, твърдия диск и паметта. Споделянето на такъв ресурс се нуждае от опашка. Компютърните периферни устройства трябва да прекъсват компютъра от време на време. Прекъсванията трябва да се обработват по същия начин, по който са пристигнали. Това се нуждае от опашка. Опашката може да се използва например за управление на файлове с приложения за работа, ако файловете се съхраняват в компютъра. Опашката е структура от данни със списък, която е или единично свързан списък, или двойно свързан списък. По правило първият елемент, който влиза в списъка, е първият елемент, който излиза. C ++ предоставя структура от данни на опашката в стандартната си библиотека. Категориите функции и оператори -членове, достъпни за тази структура, са изграждане на опашки, достъп до елементите на опашката, капацитет на опашката, модификатори на опашки и оператори с претоварване на опашката. Всяка структура от данни на опашката трябва да осигурява поне функциите push () и pop (). push () означава изпращане на нов елемент в задната част на опашката; и pop () означава премахване на елемента, който е в предната част на опашката. За съжаление, в C ++ тези функции не връщат изтласканата или изскочилата стойност. Така че, за да знаете последния елемент преди натискане, трябва да се използва допълнителната функция back (); и за да знаете първия елемент преди изскачането, трябва да се използва допълнителната функция front (). Стойността е за тип данни, както създаденият обект е за клас. Така че, определен клас може да се използва като тип данни за създаване на шаблон за опашка. Различните обекти за класа стават като различни стойности за класа. Опашката има приложения на компютъра. Може да се използва например за управление на файлове с приложения за работа, ако файловете се съхраняват в компютъра. Крис
опашка<const char*>това2({„зъл“});
intникой=че 1>това2;
цена<<никой<< 'н';
опашка<const char*>това2({„зъл“});
intникой=че 1<=това2;
цена<<никой<< 'н';
опашка<const char*>това2({„зъл“});
intникой=че 1> =това2;
цена<<никой<< 'н'; Класът и неговите инстанцирани обекти
#включва
използвайки пространство за имена std;
клас TheCla
{
обществен:
intникой;
статичен charгл;
невалиденфункция(charне, const char *стр)
{
цена<< 'Има ' <<никой<< 'книги на стойност' <<не<<стр<< ' в магазина.' << 'н';
}
статичен невалидензабавно(charгл)
{
ако (гл== 'да се')
цена<< „Официална статична функция -член“ << 'н';
}
};
intглавен()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
опашка<TheCla>че;
че.бутане(obj1);че.бутане(obj2);че.бутане(obj3);че.бутане(obj4);че.бутане(obj5);
цена<<че.размер() << 'н';
връщане 0;
} Свързан списък
Приложения на опашката
Споделяне на компютърни ресурси
Обработка на прекъсвания
Управление на информацията.
Заключение