Przejdź do zawartości

Struktury danych/Kolejki/Kolejka podwójna

Z Wikibooks, biblioteki wolnych podręczników.
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

[edytuj]
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

[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]