[Powered by Google Translate] [Kolejka] [Chris Gerber, Harvard University] To CS50, CS50.TV] Jednym z przydatnych struktura danych do przechowywania uporządkowaną kolekcję elementów jest kolejka. To jest, gdy stosuje się elementy muszą być usunięte w tej samej kolejności, w jakiej zostały dodane. Koncepcja ta jest dalej FIFO, co jest skrótem od najpierw, pierwszy na wyjściu. Aby wyobrazić to może być użyteczne dla obrazu linia kasy w sklepie. Jak ludzie przybywają, czekają na końcu linii. Kasjer następnie bierze zakręty obsługujących klientów z przodu, którzy następnie opuścić jednej linii na raz. Informatykę, odwołujemy się do przodu, jak kolejki głowicy i ponownie w ogonie. Przykład, gdy może to wykorzystać w zastosowaniu liście oczekujących jest dla rejestracji klasy. Jak fotele będą dostępne w klasie, osób na czele listy oczekujących jest możliwość, aby zapisać się w klasie. 

Kolejka może być wykonana przy użyciu dowolnej kolekcji , który przechowuje dane w celu, na przykład w formie tablicy lub liście połączonej. Wraz z kolekcji do przechowywania elementów w kolejce, muszą również metodę wprowadzania pozycji na koniec kolejki który nazywa enqueuing, a co innego usunąć element z głowy kolejki, które nazywa się z kolejki. Często przydatne jest włączenie innej metody zwraca bieżącą długość kolejki jak również metody, aby sprawdzić, czy kolejka jest pusta. Przyjrzyjmy się, w jaki sposób możemy zaimplementować kolejkę liczb całkowitych w C, za pomocą tablicy zbierania elementów. Po pierwsze, stworzenie struktury o nazwie kolejka trzymać nasze zmienne. Użyjemy ustalony rozmiar tablicy indeksu 0 liczb całkowitych do przechowywania elementów. Zostanie również zmienną głowę która przechowuje indeks elementu, który jest obecnie na czele kolejki. Trzecia zmienna, zwany długość, stosowany będzie aby śledzić liczbę elementów w tablicy. Jako alternatywę, można rozważyć użycie zmienną ogon zwrócić się do ostatniego elementu pola w tablicy. Zanim napiszemy dowolną więcej kodu, Spróbujmy nasz projekt. Zacznijmy pustą tablicę o długości 0, z głową ustawić na 0. Teraz enqueue 4 wartości - 6, 2, 3, i 1. Długość będzie teraz 4 i głowa pozostanie na 0. 

Co się stanie, jeśli usunie z niej wartość? Będziemy skrócenia do 3, ustawić głowicę na 1, i zwrócić wartość 6. Ten kod może wyglądać tak. Tutaj mamy rozkolejkowania funkcji która przyjmuje wskaźnik do kolejki - q - oraz wskaźnik do elementu, która jest typu int. Najpierw musimy sprawdzić długość kolejki, aby upewnić się, że to więcej niż 0, w celu zapewnienia, że ​​jest to element do rozkolejkowywana. Następnie szukamy w tablicy pierwiastków, na czele pozycji, i ustawić wartość elementu jest napięcie w tej pozycji. Następnie zmienić głowę być następnym index % Pojemności. Następnie zmniejsza długość kolejki do 1. Wreszcie, zwraca true wskazuje, że Dequeue pomyślnie. Jeśli z kolejki ponownie będzie długość 2 głowa stanie się również 2, zwracana wartość będzie 2. 

Co się stanie, jeśli enqueue innej wartości takie jak 7? Jak było na końcu kolejki, musimy owinąć wokół i przechowywać wartość w 0 element tablicy. Matematycznie można to reprezentowane przez dodanie długość wskaźnikowi głowy i wykonując moduł używając zdolności kolejki. Tutaj jest 2 +2, która jest o 4% 4 które jest 0. Przełożenie tego pomysłu do kodu mamy tę funkcję. Tutaj widzimy Dodaje funkcję, która przyjmuje wskaźnik do kolejki - Q - i ma element do kolejkowane, która jest liczbą całkowitą. Kolejnym upewnij się, że pojemność kolejki jest w dalszym ciągu większe niż aktualna długość kolejki. Następnie element przechowywane w tablicy elementów w którym indeks jest określona przez długość głowicy +% ilość kolejki. Następnie zwiększyć długość kolejki, 1, , a następnie powrót do wskazania, że ​​prawdziwe enqueue funkcja zakończyła się pomyślnie. 

Oprócz tych dwóch funkcji już wspomnieliśmy, istnieją dwie dodatkowe funkcje. Pierwszym jest funkcja isempty, która przyjmuje wskaźnik do kolejki i sprawdza, czy jest 0 długości. Drugi jest funkcją długości, która również ma wskaźnik do kolejki i zwraca bieżącą długość od struktury. Ten krótki przegląd wykazał, jedną z możliwych realizacji kolejce. Jednym z ograniczeń tej realizacji że kolejka ma stały rozmiar maksymalną. Jeśli staramy się dodać więcej elementów niż kolejka może pomieścić, może musimy zignorować żądanie i upuścić element, lub może wolimy wrócić jakiś rodzaj błędu. Korzystanie z połączonej listy zamiast tablicy byłoby łatwiej dynamicznie rozmiaru kolejki. Jednak, ponieważ nie mamy bezpośredniego dostępu do elementów połączonej listy, jeśli nie będziemy śledzić ogona, musielibyśmy skanowanie całego połączonej listy, aby dostać się do końca za każdym razem. Możemy również rozważyć użycie tablicy inny typ danych, np. elemencie, do tworzenia elementów kolejki bardziej złożonych. Wracając do naszego przykładu z listy oczekujących klasy, Struktury te mogą reprezentować poszczególne studentów. 

Nazywam się Chris Gerber, i to jest CS50. [CS50.TV] I powraca - >> Jeszcze raz. I powrót do wskazania, że ​​prawdziwe - kolejka była sukcesem. -% Ilość kolejki - To będzie zabawa w edycji. [Śmiech]