Stos a kolejka
Stos jest uporządkowaną listą, w której wstawianie i usuwanie elementów listy może odbywać się tylko na jednym końcu zwanym górą. Z tego powodu stos jest uważany za strukturę danych Last in First out (LIFO). Kolejka to także uporządkowana lista, w której wstawianie elementów listy odbywa się na jednym końcu zwanym tyłem, a usuwanie elementów odbywa się na drugim końcu zwanym frontem. Ten mechanizm wstawiania i usuwania sprawia, że kolejka jest strukturą danych First in First out (FIFO).
Co to jest stos?
Jak wspomniano wcześniej, stos to struktura danych, w której elementy są dodawane i usuwane tylko z jednego końca zwanego szczytem. Stosy umożliwiają tylko dwie podstawowe operacje zwane push i pop. Operacja push dodaje nowy element na górę stosu. Operacja pop usuwa element ze szczytu stosu. Jeśli stos jest już pełny, podczas wykonywania operacji wypychania jest to traktowane jako przepełnienie stosu. Jeśli operacja pop jest wykonywana na już pustym stosie, jest ona uważana za niedopełnienie stosu. Ze względu na niewielką liczbę operacji, które można wykonać na stosie, jest on uważany za strukturę danych o ograniczonym dostępie. Dodatkowo, zgodnie ze sposobem zdefiniowania operacji push i pop, jasne jest, że elementy, które zostały dodane do stosu jako ostatnie, wychodzą ze stosu jako pierwsze. Dlatego stos jest uważany za strukturę danych LIFO.
Co to jest kolejka?
W kolejce elementy są dodawane z tyłu kolejki i usuwane z przodu kolejki. Ponieważ elementy, które zostaną dodane jako pierwsze, zostaną najpierw usunięte z kolejki, zachowuje kolejność FIFO. Ze względu na tę kolejność dodawania i usuwania elementów, kolejka reprezentuje ideę linii kasowej. Ogólne operacje obsługiwane przez kolejkę to operacje en-queue i de-queue. Operacja en-queue doda element z tyłu kolejki, podczas gdy operacja usunięcia z kolejki usunie element z przodu kolejki. Ogólnie rzecz biorąc, kolejki nie mają limitu liczby elementów, które można dodać do kolejki poza ograniczeniami pamięci.
Jaka jest różnica między stosem a kolejką?
Mimo że zarówno stosy, jak i kolejki są rodzajami uporządkowanych list, mają pewne istotne różnice. W stosach dodawanie lub usuwanie elementów może odbywać się tylko z jednego końca zwanego górą, podczas gdy w kolejkach dodawanie elementów odbywa się z jednego końca zwanego tyłem, a usuwanie elementów odbywa się z drugiego końca zwanego frontem. W stosie elementy, które są dodawane jako ostatnie, są usuwane ze stosu jako pierwsze. Dlatego stos jest uważany za strukturę danych LIFO. W kolejkach pozycje dodane jako pierwsze zostaną najpierw usunięte z kolejki. Dlatego kolejka jest uważana za strukturę danych FIFO.
Powiązany link:
Różnica między stosem a stertą
