Struktury danych/Kolejki/Kolejka podwójna
Spis treści | |
Wstęp | |
Struktury danych |
Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy |
Dodatki |
Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika |
Kolejka podwójna
[edytuj]Kolejnym rodzajem kolejki jest kolejka podwójna (ang. deque albo dequeue od double-ended queue), jest to pewnego rodzaju uogólnienie wcześniejszej struktury. W kolejce podwójnej można dodawać na początek oraz na koniec, podobnie jest z usuwaniem elementów. Można też dostrzec w tej strukturze pewne analogie do listy.
Kolejka podwójna
- INJECT(S:kolejka, d:Data) - dodaj na koniec kolejki
- EJECT(S:kolejka) - usuń z końca kolejki
- PUSH(S:kolejka, d:Data) - dodaj do początku kolejki
- POP(S:kolejka) - usuń z początku kolejki
- FRONT(S:kolejka) - podejrzyj pierwszy element
- BACK(S:kolejka) - podejrzyj ostatni element
Rodzaje
[edytuj]Istnieją pewne typy kolejek podwójnych :
- Deque z ograniczeniem wejścia to taka, gdzie usuwanie można przeprowadzać na obu końcach, jednak dodawanie może być wykonane tylko na jednym końcu.
- Deque z ograniczeniem wyjścia to taka, gdzie dodawanie można przeprowadzać na obu końcach, ale usuwanie może być wykonane tylko na jednym końcu.
Wszystkie podstawowe struktury liniowe mogę być rozważane jako pewne specjalizacje kolejki podwójnej. Można je również implementować za jej pomocą.
Implementacja
[edytuj]W przygotowaniu: Opisać i dodać implementację w C++ |