Wstęp
Kolejka to zbiór elementów, w którym pierwszy element dodany do listy musi być pierwszym elementem, który zostanie usunięty w następnej kolejności. Tak więc w miarę dodawania przedmiotów do kolekcji, powiększa się ona, czyli rośnie. Ilekroć jakakolwiek pozycja ma zostać usunięta, musi być dodana jako pierwsza. Jeśli przedmioty są usuwane w sposób ciągły, to następny usuwany jest drugim elementem; trzeci jest usuwany później i tak dalej.
Po usunięciu pierwszej pozycji z oryginalnej listy, druga staje się pierwszą pozycją. Po usunięciu drugiej pozycji trzecia staje się pierwszą i tak dalej.
Dobrym przykładem kolejki z życia jest sytuacja, w której ludzie ustawiają się w kolejce, aby poczekać na usługę lub dobro. Pierwsza osoba jest obsługiwana jako pierwsza przed ostatnią. Jednak kolejka, o której mowa w tym samouczku, to kolejka programowa zaprojektowana w C++.
FIFO
FIFO oznacza pierwszy wszedł, pierwszy wyszedł. To kolejny sposób na docenienie kolejki. Oznacza to, że pierwsza pozycja, która zostanie umieszczona na liście, jest pierwszą, która zostanie usunięta, za każdym razem, gdy ma nastąpić usunięcie. Początek listy nazywa się głową lub frontem; koniec listy nazywa się tyłem lub ogonem.
Niezbędne operacje
Kolejka oprogramowania musi zawierać co najmniej następujące operacje:
naciskać
Ta operacja dodaje nowy element z tyłu kolejki. Ta operacja jest oficjalnie nazywana kolejką.
Zmiana
Ta operacja usuwa pierwszy element kolejki, a drugi element staje się nowym pierwszym elementem. Ta operacja nazywa się oficjalnie dequeue. Nazywa się pop w C++.
W tym artykule wyjaśniono, jak używać struktury danych kolejki C++. Aby zrozumieć resztę tego artykułu, powinieneś znać wskaźniki i referencje C++.
Klasa i przedmioty
Klasa to zbiór współpracujących ze sobą zmiennych i funkcji, do których nie przypisano wartości. Kiedy wartości są przypisane do zmiennych, klasa staje się obiektem. Różne wartości przypisane do tej samej klasy skutkują różnymi obiektami; oznacza to, że różne obiekty są tą samą klasą o różnych wartościach. Mówi się, że tworzenie obiektu z klasy jest tworzeniem instancji obiektu.
Nazwa, kolejka, to klasa. Obiekt utworzony z klasy kolejki ma nazwę wybraną przez programistę.
Funkcja należąca do klasy jest potrzebna do utworzenia instancji obiektu z klasy. W C++ ta funkcja ma taką samą nazwę jak nazwa klasy. Obiekty utworzone (instancja) z klasy mają różne nazwy nadawane im przez programistę.
Tworzenie obiektu z klasy oznacza konstruowanie obiektu; oznacza to również tworzenie instancji.
Program w C++, który używa klasy kolejki, zaczyna się następującymi wierszami na początku pliku:
#włączać#włączać
używając standardowej przestrzeni nazw;
Pierwsza linia dotyczy wejścia/wyjścia. Druga linia to umożliwienie programowi korzystania ze wszystkich funkcji klasy kolejki. Trzecia linia pozwala programowi na używanie nazw w standardowej przestrzeni nazw.
Przeciążanie funkcji
Gdy dwie lub więcej różnych sygnatur funkcji ma tę samą nazwę, mówi się, że nazwa ta jest przeciążona. Gdy wywoływana jest jedna funkcja, liczba i typ argumentów określają, która funkcja jest faktycznie wykonywana.
Budowa
kolejka<rodzaj>Nazwa()Poniższa deklaracja tworzy instancję kolejki o nazwie que typu int.
kolejka<int>że;Kolejka jest pusta. Deklaracja zaczyna się od słowa zastrzeżonego, kolejki, po której następuje nawias ostry z typem danych. Następnie masz nazwę podaną przez programistę dla kolejki.
Konstruowanie z listą inicjatorów
Poniższa definicja pokazuje, jak utworzyć kolejkę z listą inicjatorów:
kolejka<pływak>że({1,1, 2.2, 3,3, 4.4});Niszczenie kolejki
Aby zniszczyć kolejkę, po prostu pozwól jej wyjść poza zakres.
Dostęp do elementu kolejki
wciśnij(wartość)
Kolejka to lista „pierwszy wszedł, pierwszy wyszedł”. Tak więc każda wartość jest dodawana od tyłu. Poniższy segment kodu tworzy pustą kolejkę, po której od tyłu dodawanych jest pięć wartości zmiennoprzecinkowych:
kolejka<pływak>że;że.naciskać(1,1);
że.naciskać(2.2);
że.naciskać(3,3);
że.naciskać(4.4);
że.naciskać(5,5);
size() const
Zwraca liczbę elementów w kolejce. Poniższy kod ilustruje:
kolejka<pływak>że;że.naciskać(1,1);że.naciskać(2.2);że.naciskać(3,3);że.naciskać(4.4);że.naciskać(5,5);
koszt<<że.rozmiar() << ' ';
Wyjście to 5.
z przodu()
Zwraca to odwołanie do pierwszego elementu kolejki bez usuwania elementu. Dane wyjściowe poniższego kodu to 1.1.
kolejka<pływak>że;że.naciskać(1,1);że.naciskać(2.2);że.naciskać(3,3);że.naciskać(4.4);że.naciskać(5,5);
koszt<<że.z przodu() << ' ';
Element nie jest usuwany z kolejki.
front() const
Gdy konstrukcja kolejki jest poprzedzona przez const, zamiast front() wykonywane jest wyrażenie front() const. Jest używany na przykład w poniższym kodzie.
stałykolejka<pływak>że({1,1, 2.2, 3,3, 4.4, 5,5});koszt<<że.z przodu() << ' ';
Zwracane jest stałe odwołanie. Element nie jest usuwany z wektora. Nie można zmienić elementów kolejki.
plecy()
Zwraca to odwołanie do ostatniego elementu kolejki, bez usuwania elementu. Wyjście poniższego kodu to 5.5.
kolejka<pływak>że;że.naciskać(1,1);że.naciskać(2.2);że.naciskać(3,3);że.naciskać(4.4);że.naciskać(5,5);
koszt<<że.plecy() << ' ';
back() const
Gdy konstrukcja kolejki jest poprzedzona const, zamiast back() wykonywane jest wyrażenie back() const. Jest używany na przykład w poniższym kodzie.
stałykolejka<pływak>że({1,1, 2.2, 3,3, 4.4, 5,5});koszt<<że.plecy() << ' ';
Zwracane jest stałe odwołanie. Element nie jest usuwany z kolejki. Z poprzednim const dla konstrukcji kolejki, elementy w kolejce nie mogą być zmieniane.
Pojemność kolejki
size() const
- patrz wyżej
pusty() const
Zwraca 1 dla true, jeśli nie ma żadnych elementów w kolejce, lub 0 dla false, jeśli kolejka jest pusta. Poniższy kod ilustruje to:
kolejka<pływak>że1({1,1, 2.2, 3,3, 4.4, 5,5});koszt<<że1.pusty() << ' ';
kolejka<pływak>to2;
koszt<<że2.pusty() << ' ';
Dane wyjściowe to:
01
Modyfikatory kolejki
Muzyka pop ()
Kolejka to FIFO, więc każdy element, który ma zostać usunięty, musi zostać usunięty z góry (głowia) kolejki. Ta funkcja członkowska usuwa pierwszy element bez zwracania go. Poniższy kod ilustruje to:
kolejka<pływak>że({1,1, 2.2, 3,3, 4.4, 5,5});koszt<<że.z przodu() << ' ';
że.Muzyka pop();
koszt<<że.rozmiar() << ' ';
Dane wyjściowe to:
1,14
zamiana(b)
Można zamienić dwie kolejki, jak pokazano w tym segmencie kodu:
kolejka<pływak>że1({1,1, 2.2, 3,3, 4.4, 5,5});kolejka<pływak>to2({10, 20});
że1.zamieniać(to2);
koszt<< 'Pierwszy element i rozmiar que1:
'<<że1.z przodu() <<','<<że1.rozmiar() << ' ';
koszt<< 'Pierwszy element i rozmiar que2'<<
że2.z przodu() <<','<<że2.rozmiar() << ' ';
Dane wyjściowe to:
Pierwszy element i rozmiar que1: 10, 2
Pierwszy element i rozmiar que2: 1,1, 5
Zwróć uwagę, że w razie potrzeby długość kolejki jest zwiększana. Ponadto wartości, które nie miały zamienników, są zastępowane jakąś wartością domyślną. Typy danych muszą być tego samego typu.
Operatory równości i relacyjne dla kolejek
W przypadku zwykłych znaków w C++, w porządku rosnącym, liczby poprzedzają wielkie litery, które poprzedzają małe litery. Znak spacji występuje przed zerem i wszystkimi.
Operatory równości
Zwraca 1 dla prawdy i 0 dla fałszu.
== Operator
Zwraca 1, jeśli dwie kolejki mają ten sam rozmiar, a odpowiadające im elementy są równe; w przeciwnym razie zwraca 0. Przykład:
kolejka<stały zwęglać*>że1({'uprzejmy', 'coś innego'});kolejka<stały zwęglać*>to2({'niegodziwy'});
intna jednego=że1==to2;
koszt<<na jednego<< ' ';
Wyjście to: 0.
Operator !=
– przeciwieństwo powyższego. Przykład:
kolejka<stały zwęglać*>że1({'uprzejmy', 'coś innego'});kolejka<stały zwęglać*>to2({'niegodziwy'});
intna jednego=że1! =to2;
koszt<<na jednego<< ' ';
Dane wyjściowe to: 1.
Operatorzy relacyjni
Zwraca 1 dla prawdy i 0 dla fałszu.
ten
Zwraca 1, jeśli pierwsza kolejka jest początkowym podzbiorem drugiej kolejki, a elementy dwóch równych części są takie same iw tej samej kolejności. Jeśli obie kolejki mają ten sam rozmiar lub różne rozmiary i poruszając się od lewej do prawej, napotkany element w pierwszej kolejce jest mniejszy niż odpowiadający mu element w drugiej kolejce, to nadal zostanie zwrócone 1. W przeciwnym razie zwracane jest 0. Przykład:
kolejka<stały zwęglać*>że1({'uprzejmy', 'coś innego'});kolejka<stały zwęglać*>to2({'niegodziwy'});
intna jednego=że1<to2;
koszt<<na jednego<< ' ';
Wyjście to 1. > Operator – przeciwieństwo powyższego. Przykład: Wyjście: 0 ten<= Operator - taki sam jak Wyjście: 1 >= Operator – przeciwieństwo powyższego. Przykład: Wyjście: 0 Wartość odnosi się do typu danych, tak jak skonkretyzowany obiekt do klasy. Konstrukcja kolejki może również akceptować klasę jako typ danych. Poniższy program ilustruje to: Wyjście to 5. Lista kolejek jest technicznie nazywana listą połączoną. Istnieją dwa rodzaje połączonych list dla kolejki: pojedynczo połączona lista i podwójnie połączona lista. Pojedynczo połączony element listy może być zaimplementowany przez strukturę dwóch członków. Jeden składnik przechowuje wskaźnik do następnego elementu, a drugi składnik przechowuje dane (liczba pojedyncza dla danych). Podwójnie połączony element listy może być zaimplementowany przez strukturę złożoną z trzech członków. Środkowy element zawiera odniesienie, podczas gdy pierwszy i trzeci element przechowują wskaźniki do sąsiednich elementów. Kolejka jest strukturą danych typu „pierwsze weszło-pierwsze wyszło”. W informatyce zdarzają się sytuacje, w których dane docierają w postaci kolejki, co wymaga zachowania „pierwsze weszło-pierwsze wyszło”. Zasób w komputerze to dowolny fizyczny lub wirtualny składnik o ograniczonej dostępności. Obejmują one procesor, kartę graficzną, dysk twardy i pamięć. Udostępnianie takiego zasobu wymaga kolejki. Komputerowe urządzenia peryferyjne muszą od czasu do czasu przerywać pracę komputera. Przerwania muszą być obsługiwane w ten sam sposób, w jaki przyszły. To wymaga kolejki. Kolejka może służyć na przykład do zarządzania plikami aplikacji dla zadania, jeśli pliki są przechowywane na komputerze. Kolejka jest listową strukturą danych, która jest listą połączoną pojedynczo lub listą połączoną podwójnie. Z reguły pierwszy element, który pojawia się na liście, jest pierwszym, który wychodzi. C++ zapewnia strukturę danych kolejki w swojej standardowej bibliotece. Kategorie funkcji składowych i operatorów dostępnych dla tej struktury to budowa kolejki, dostęp do elementu kolejki, pojemność kolejki, modyfikatory kolejek i operatory przeciążone kolejką. Każda struktura danych kolejki musi zapewniać co najmniej funkcje składowe push() i pop(). push() oznacza wysłanie nowego elementu z tyłu kolejki; a pop() oznacza usunięcie elementu znajdującego się na początku kolejki. Niestety w C++ te funkcje nie zwracają wartości push lub popped. Tak więc, aby poznać ostatni element przed wypchnięciem, należy użyć dodatkowej funkcji back(); i aby poznać pierwszy element przed pojawieniem się, należy użyć dodatkowej funkcji front(). Wartość odnosi się do typu danych, tak jak skonkretyzowany obiekt do klasy. Tak więc konkretna klasa może być używana jako typ danych do tworzenia instancji szablonu kolejki. Różne obiekty dla klasy stają się jak różne wartości dla klasy. Kolejka ma aplikacje na komputerze. Może być używany na przykład do zarządzania plikami wniosków o pracę, jeśli pliki są przechowywane na komputerze. Chrys
kolejka<stały zwęglać*>to2({'niegodziwy'});
intna jednego=że1>to2;
koszt<<na jednego<< '
';
kolejka<stały zwęglać*>to2({'niegodziwy'});
intna jednego=że1<=to2;
koszt<<na jednego<< '
';
kolejka<stały zwęglać*>to2({'niegodziwy'});
intna jednego=że1> =to2;
koszt<<na jednego<< '
'; Klasa i jej obiekty instancyjne
#włączać
używając standardowej przestrzeni nazw;
klasa TheCla
{
publiczny:
intna jednego;
statyczny zwęglaćch;
próżniafunkcjonować(zwęglaćnie, stały zwęglać *P)
{
koszt<< 'Są ' <<na jednego<< ' książki warte ' <<nie<<P<< ' w sklepie.' << '
';
}
statyczny próżniazabawa(zwęglaćch)
{
Jeśli (ch== 'do')
koszt<< „Oficjalna statyczna funkcja składowa” << '
';
}
};
intGłówny()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
kolejka<TheCla>że;
że.naciskać(obj1);że.naciskać(obj2);że.naciskać(obj3);że.naciskać(obj4);że.naciskać(obj5);
koszt<<że.rozmiar() << '
';
powrót 0;
} Połączona lista
Zastosowania kolejki
Udostępnianie zasobów komputerowych
Obsługa przerwań
Zarządzaj informacjami.
Wniosek