Różnica między stosem a kolejką

Autor: Laura McKinney
Data Utworzenia: 2 Kwiecień 2021
Data Aktualizacji: 16 Móc 2024
Anonim
Różnica między stosem a kolejką - Technologia
Różnica między stosem a kolejką - Technologia

Zawartość


Stos i kolejka to nieprymitywne struktury danych. Główne różnice między stosem a kolejką polegają na tym, że stos używa metody LIFO (ostatnie weszło pierwsze wyszło), aby uzyskać dostęp i dodać elementy danych, natomiast kolejka używa metody FIFO (pierwsze weszło pierwsze wyszło), aby uzyskać dostęp i dodać elementy danych.

Stos ma tylko jeden koniec otwarty do przepychania i usuwania elementów danych, z drugiej strony Kolejka ma oba końce otwarte do kolejkowania i usuwania z kolejki elementów danych.

Stos i kolejka są strukturami danych używanymi do przechowywania elementów danych i są w rzeczywistości oparte na odpowiedniku w świecie rzeczywistym. Na przykład stos to stos płyt CD, na którym można wyjąć i włożyć płytę CD przez wierzch stosu płyt CD. Podobnie, kolejka jest kolejką na bilety do teatru, w której osoba stojąca na pierwszym miejscu, tj. Przód kolejki, zostanie obsłużona jako pierwsza, a nowa osoba pojawiająca się pojawi się z tyłu kolejki (tylny koniec kolejki).


  1. Wykres porównania
  2. Definicja
  3. Kluczowe różnice
  4. Realizacja
  5. Operacje
  6. Aplikacje
  7. Wniosek

Wykres porównania

Podstawa do porównaniaStos Kolejka
Zasada działaniaLIFO (Last in First out)FIFO (First in First out)
StrukturaTen sam koniec służy do wstawiania i usuwania elementów.Jeden koniec służy do wkładania, tj. Tylny koniec, a drugi koniec służy do usuwania elementów, tj. Przedniego końca.
Liczba użytych wskaźnikówJedenDwa (w prostej kolejce)
Operacje wykonanePush and Pop Kolejkuj i usuwaj z kolejki
Badanie stanu pustegoGóra == -1Przód == -1 || Przód == Tył + 1
Badanie pełnego stanu
Góra == Maks. - 1Tył == maks. - 1
WariantyNie ma wariantów.Ma warianty takie jak kolejka cykliczna, kolejka priorytetowa, kolejka podwójnie zakończona.
RealizacjaProstszeStosunkowo skomplikowane


Definicja stosu

Stos to nieprymitywna liniowa struktura danych. Jest to uporządkowana lista, na której dodawany jest nowy element, a istniejący element jest usuwany tylko z jednego końca, nazywanego jako wierzchołek stosu (TOS). Ponieważ całe usuwanie i wstawianie do stosu odbywa się od góry stosu, ostatni dodany element będzie pierwszym, który zostanie usunięty ze stosu. Dlatego stos nazywany jest listą typu Last-in-First-out (LIFO).

Zauważ, że element często dostępny na stosie jest najwyższym elementem, podczas gdy ostatni dostępny element znajduje się na dole stosu.

Przykład

Niektórzy z was mogą jeść herbatniki (lub Poppins). Jeśli przypuszczasz, tylko jedna strona pokrywy jest rozdarta, a herbatniki są wyjmowane jeden po drugim. To się nazywa popping i podobnie, jeśli chcesz zachować jakieś ciastka na jakiś czas później, umieścisz je z powrotem w paczce, ponieważ ten sam rozdarty koniec nazywa się pchaniem.

Definicja kolejki

Kolejka jest liniową strukturą danych należącą do kategorii typu nie-pierwotnego. Jest to zbiór podobnych elementów. Dodanie nowych elementów odbywa się na jednym końcu zwanym tylnym końcem. Podobnie, usuwanie istniejących elementów odbywa się na drugim końcu zwanym Front-end, i logicznie jest to lista typu FIFO.

Przykład

W naszym codziennym życiu spotykamy się z wieloma sytuacjami, w których czekamy na pożądaną usługę, tam musimy stanąć w kolejce, aby nasza kolej została obsłużona. Ta kolejka oczekiwania może być traktowana jako kolejka.

  1. Z drugiej strony stos podąża za mechanizmem LIFO. Kolejka podąża za mechanizmem FIFO, aby dodawać i usuwać elementy.
  2. W stosie ten sam koniec służy do wstawiania i usuwania elementów. Przeciwnie, w kolejce używane są dwa różne końce do wstawiania i usuwania elementów.
  3. Ponieważ stos ma tylko jeden otwarty koniec, to jest powód, dla którego używa się tylko jednego wskaźnika do odniesienia do góry stosu. Ale kolejka używa dwóch wskaźników w odniesieniu do przedniej i tylnej części kolejki.
  4. Stos wykonuje dwie operacje znane jako push i pop, podczas gdy w kolejce jest znany jako enqueue i dequeue.
  5. Implementacja stosu jest łatwiejsza, natomiast implementacja kolejki jest trudna.
  6. Kolejka ma warianty, takie jak kolejka cykliczna, kolejka priorytetowa, kolejka podwójnie zakończona itp. Natomiast stos nie ma wariantów.

Implementacja stosu

Stos można zastosować na dwa sposoby:

  1. Implementacja statyczna używa tablic, aby utworzyć stos. Implementacja statyczna jest techniką bez wysiłku, ale nie jest elastycznym sposobem tworzenia, ponieważ deklaracja wielkości stosu musi być dokonana podczas projektowania programu, po czym nie można zmieniać wielkości. Ponadto statyczna implementacja nie jest bardzo wydajna w zakresie wykorzystania pamięci. Ponieważ tablica (do implementacji stosu) jest deklarowana przed rozpoczęciem operacji (w czasie projektowania programu). Teraz, jeśli liczba elementów do sortowania jest bardzo mniejsza na stosie, statycznie przydzielona pamięć zostanie zmarnowana. Z drugiej strony, jeśli na stosie będzie przechowywana większa liczba elementów, nie będziemy w stanie zmienić rozmiaru tablicy, aby zwiększyć jej pojemność, aby mogła pomieścić nowe elementy.
  2. Dynamiczna implementacja jest również nazywany reprezentacją listy połączonej i używa wskaźników do implementacji struktury danych typu stosu.

Implementacja kolejki

Kolejkę można wdrożyć na dwa sposoby:

  1. Implementacja statyczna: Jeśli kolejka jest implementowana przy użyciu tablic, dokładna liczba elementów, które chcemy przechowywać w kolejce, musi być zapewniona wcześniej, ponieważ rozmiar tablicy musi zostać zadeklarowany w czasie projektowania lub przed rozpoczęciem przetwarzania. W takim przypadku początek tablicy stanie się przednią częścią kolejki, a ostatnia lokalizacja tablicy będzie działała jako tylna część kolejki. Poniższa relacja pokazuje, że całe elementy istnieją w kolejce, gdy są implementowane za pomocą tablic:
    przód - tył + 1
    Jeśli „tył <przód”, nie będzie elementu w kolejce lub kolejka zawsze będzie pusta.
  2. Dynamiczna implementacja: Wdrażając kolejki za pomocą wskaźników, główną wadą jest to, że węzeł w połączonej reprezentacji zajmuje więcej miejsca w pamięci niż odpowiedni element w reprezentacji tablicowej. Ponieważ w każdym węźle znajdują się co najmniej dwa pola, jedno dla pola danych, a drugie do przechowywania adresu następnego węzła, podczas gdy w reprezentacji połączonej istnieje tylko pole danych. Zalety korzystania z połączonej reprezentacji stają się oczywiste, gdy wymagane jest wstawienie lub usunięcie elementu pośrodku grupy innych elementów.

Operacje na stosie

Podstawowe operacje, które można obsługiwać na stosie, są następujące:

  1. PCHAĆ: kiedy nowy element jest dodawany na górze stosu, jest znany jako operacja PUSH. Wciśnięcie elementu na stos powoduje wywołanie dodania elementu, ponieważ nowy element zostanie wstawiony u góry. Po każdej operacji push góra jest zwiększana o jeden. Jeśli tablica jest pełna i nie można dodać żadnego nowego elementu, nazywa się to warunkiem STOSOWANIE-PEŁNĄ lub PRZEPŁYWEM STOSOWANIA. DZIAŁANIE PUSH - funkcja w C:
    Biorąc pod uwagę stos jest zadeklarowany jako
    int stos, top = -1;
    void push ()
    {
    element int;
    jeśli (góra <4)
    {
    f („Wprowadź liczbę”);
    skan („% d” i pozycja);
    góra = góra + 1;
    stos = przedmiot;
    }
    jeszcze
    {
    f („Stos jest pełny”);
    }
    }
  2. MUZYKA POP: Element usuwany z góry stosu nazywany jest operacją POP. Stos jest zmniejszany o jeden, po każdej operacji pop. Jeśli na stosie nie pozostanie żaden element, a pop zostanie wykonany, spowoduje to warunek STACK UNDERFLOW, co oznacza, że ​​twój stos jest pusty. OPERACJA POP - funkcje w C:
    Biorąc pod uwagę stos jest zadeklarowany jako
    int stos, top = -1;
    void pop ()
    {
    element int;
    jeśli (góra> = 4)
    {
    item = stos;
    góra = góra - 1;
    f („Usunięta liczba to =% d”, pozycja);
    }
    jeszcze
    {
    f („Stos jest pusty”);
    }
    }

Operacje na kolejce

Podstawowe operacje, które można wykonać w kolejce, to:

  1. Kolejkuj: Aby wstawić element do kolejki. Usuwanie operacji z C w:
    Kolejka jest zadeklarowana jako
    kolejka int, przód = -1 i tył = -1;
    void add ()
    {
    element int;
    jeśli (tył <4)
    {
    f („Wprowadź liczbę”);
    skan („% d” i pozycja);
    if (przód == -1)
    {
    przód = 0;
    tył = 0;
    }
    jeszcze
    {
    tył = tył + 1;
    }
    kolejka = pozycja;
    }
    jeszcze
    {
    f („Kolejka jest pełna”);
    }
    }
  2. Dequeue: Aby usunąć element z kolejki. Usuwanie operacji w C:
    Kolejka jest zadeklarowana jako
    kolejka int, przód = -1 i tył = -1;
    void delete ()
    {
    element int;
    if (przód! = -1)
    {
    item = kolejka;
    jeśli (przód == tył)
    {
    przód = -1;
    tył = -1;
    }
    jeszcze
    {
    przód = przód + 1;
    f („Usunięta liczba to =% d”, pozycja);
    }
    }
    jeszcze
    {
    f („Kolejka jest pusta”);
    }
    }

Zastosowania stosu

  • Analiza składniowa w kompilatorze.
  • Maszyna wirtualna Java.
  • Cofnij w edytorze tekstu.
  • Przycisk Wstecz w przeglądarce internetowej.
  • Język PostScript dla ers.
  • Implementowanie wywołań funkcji w kompilatorze.

Aplikacje kolejki

  • Bufory danych
  • Asynchroniczny transfer danych (plik IO, rury, gniazda).
  • Przydzielanie żądań do udostępnionego zasobu (er, procesor).
  • Analiza ruchu
  • Określ liczbę kasjerów w supermarkecie.

Wniosek

Stos i kolejka są liniowymi strukturami danych, które różnią się pod pewnymi względami, takimi jak mechanizm działania, struktura, implementacja, warianty, ale oba są używane do przechowywania elementów na liście i wykonywania operacji na liście, takich jak dodawanie i usuwanie elementów. Chociaż istnieją pewne ograniczenia prostej kolejki, którą można odzyskać za pomocą innych rodzajów kolejki.