Struktury danych/Kolejki/Kolejka podwójna

Spis treści
Wstęp	Wstęp - Konwencje
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

Ilustracja działania kolejki podwójnej

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

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ą.