Stos ma tylko jeden koniec otwarty do popychania i poppingu elementów danych z drugiej strony Kolejka ma oba końce otwarte do zagnieżdżania i odkładania elementów danych.
Stos i kolejka to struktury danych używane do przechowywania elementów danych i są oparte na rzeczywistych odpowiednikach świata. Na przykład stos jest stosem płyt CD, na których można wyjąć i włożyć CD na wierzch stosu płyt CD. Podobnie, kolejka jest kolejką do biletów do teatru, gdzie osoba stojąca na pierwszym miejscu, tj. Przednia strona kolejki zostanie obsłużona jako pierwsza, a nowa osoba pojawiąca się pojawi się w tylnej części kolejki (tylny koniec kolejki).
Wykres porównania
| Podstawa do porównania | Stos | Kolejka |
|---|---|---|
| Zasada działania | LIFO (Last in First out) | FIFO (pierwsze weszło pierwsze) |
| Struktura | Ten sam koniec służy do wstawiania i usuwania elementów. | Jeden koniec służy do wstawiania, tj. Tylny koniec, a drugi koniec służy do usuwania elementów, tj. Przedniego końca. |
| Liczba użytych wskaźników | Jeden | Two (w prostym przypadku kolejki) |
| Operacje wykonane | Naciśnij i pop | Zdejmij i zdejmij |
| Badanie pustego stanu | Początek == -1 | Przód == -1 || Przód == Tył + 1 |
| Badanie pełnej kondycji | Top == Max - 1 | Tył == Max - 1 |
| Warianty | Nie ma wariantów. | Ma warianty takie jak cykliczna kolejka, kolejka priorytetowa, podwójnie zakończona kolejka. |
| Realizacja | Prostsze | Stosunkowo skomplikowane |
Definicja stosu
Stos to nieprosta liniowa struktura danych. Jest to uporządkowana lista, w której dodawany jest nowy element, a istniejący element jest usuwany tylko z jednego końca, zwanego wierzchołkiem stosu (TOS). Ponieważ usuwanie i wstawianie do stosu odbywa się od góry stosu, ostatni dodany element będzie pierwszym, który zostanie usunięty ze stosu. Z tego powodu stos jest nazywany listą typu "pierwsze weszło-pierwsze wyszło" (LIFO).
Zauważ, że elementem często dostępnym w stosie jest najwyższy element, podczas gdy ostatni dostępny element znajduje się na dole stosu.
Przykład
Niektórzy z was mogą jeść ciastka (lub Poppins). Jeśli zakładasz, tylko jedna strona okładki jest rozdarta, a herbatniki są wyjmowane jeden po drugim. To się nazywa popping, i podobnie, jeśli chcesz zachować trochę herbatników przez jakiś czas, włożysz je z powrotem do tego samego rozdartego końca, co nazywa się pchaniem.
Definicja kolejki
Kolejka jest liniową strukturą danych w kategorii typu niepochodzącego. Jest to zbiór podobnych elementów. Dodanie nowych elementów odbywa się na jednym końcu nazywanym tylnym końcem. Podobnie, usuwanie istniejących elementów odbywa się na drugim końcu zwanym Front-endem, a logicznie jest to lista typu First in first out (FIFO).
Przykład
W naszym codziennym życiu spotykamy się z wieloma sytuacjami, w których czekamy na oczekiwaną usługę, tam musimy dostać się do linii oczekiwania na naszą kolej, aby uzyskać serwis. Ta kolejka oczekiwania może być traktowana jako kolejka.
Kluczowe różnice między stosami a kolejkami
- Stos następuje za mechanizmem LIFO z drugiej strony Kolejka działa zgodnie z mechanizmem FIFO, aby dodawać i usuwać elementy.
- W stosie ten sam koniec służy do wstawiania i usuwania elementów. Wręcz przeciwnie, dwa różne końce są używane w kolejce do wstawiania i usuwania elementów.
- Ponieważ stos ma tylko jeden otwarty koniec, jest to powód używania tylko jednego wskaźnika do wskazania góry stosu. Ale kolejka używa dwóch wskaźników do określenia przedniego i tylnego końca kolejki.
- Stack wykonuje dwie operacje znane jako push i pop, podczas gdy w Queue jest znane jako kolejkowanie i usuwanie.
- Implementacja stosu jest łatwiejsza, natomiast kolejkowanie jest trudne.
- Kolejka ma warianty takie jak kolejka cykliczna, kolejka priorytetowa, podwójnie zakończona kolejka itd. Natomiast stos nie ma wariantów.
Implementacja stosu
Stos można zastosować na dwa sposoby:
- Implementacja statyczna wykorzystuje tablice do utworzenia stosu. Statyczna implementacja jest techniką bez wysiłku, ale nie jest elastycznym sposobem tworzenia, ponieważ deklaracja wielkości stosu musi być wykonana podczas projektowania programu, po tym czasie rozmiar nie może być zmieniany. Ponadto implementacja statyczna nie jest bardzo wydajna pod względem wykorzystania pamięci. Ponieważ tablica (dla implementowania stosu) jest zadeklarowana przed rozpoczęciem operacji (w czasie projektowania programu). Teraz, jeśli liczba elementów do posortowania jest znacznie mniejsza w stosie, statycznie przydzielona pamięć zostanie zmarnowana. Z drugiej strony, jeśli w stosie jest więcej elementów, które mają być przechowywane, nie możemy zmienić rozmiaru tablicy, aby zwiększyć jej pojemność, aby mógł on pomieścić nowe elementy.
- Dynamiczna implementacja jest również nazywana połączoną reprezentacją listy i używa wskaźników do implementacji struktury danych stosu.
Implementacja kolejki
Kolejkę można zaimplementować na dwa sposoby:
- Implementacja statyczna : Jeśli kolejka jest zaimplementowana przy użyciu tablic, dokładna liczba elementów, które chcemy zapisać w kolejce, musi być wcześniej zapewniona, ponieważ rozmiar tablicy musi zostać zadeklarowany w czasie projektowania lub przed rozpoczęciem przetwarzania. W takim przypadku początek tablicy stanie się początkiem kolejki, a ostatnia lokalizacja tablicy będzie działała jako tylna strona kolejki. Poniższa relacja powoduje, że całe elementy istnieją w kolejce po zaimplementowaniu za pomocą tablic:
przód - tył + 1
Jeśli "tył <przód" nie będzie elementu w kolejce lub kolejka będzie zawsze pusta. - Dynamiczna implementacja : Implementowanie kolejek za pomocą wskaźników, główną wadą jest to, że węzeł w połączonej reprezentacji zużywa więcej pamięci niż odpowiadający element w reprezentacji tablicowej. Ponieważ istnieją co najmniej dwa pola w każdym węźle jeden dla pola danych i inne dla przechowywania adresu następnego węzła, podczas gdy w połączonym przedstawieniu istnieje tylko pole danych. Zaletą korzystania z połączonej reprezentacji staje się oczywiste, gdy wymagane jest wstawienie lub usunięcie elementu w środku grupy innych elementów.
Operacje na stosie
Podstawowe operacje, które można obsługiwać na stosie, są następujące:
- PUSH : kiedy nowy element jest dodawany do wierzchołka stosu, znany jest jako operacja PUSH. Przesunięcie elementu w stos wywołuje dodanie elementu, ponieważ nowy element zostanie wstawiony u góry. Po każdej operacji wypychania góra jest zwiększana o jeden. Jeśli tablica jest pełna i nie można dodać nowego elementu, nazywa się to stanem STACK-FULL lub STACK OVERFLOW. PUSH OPERATION - funkcja w C:
Biorąc pod uwagę stos jest zadeklarowany jakoint stack [5], top = -1;void push(){int item;if (top < 4){printf ("Enter the number") ;scan ("%d", & item) ;top = top + 1;stack [top] = item;}else{printf (" Stack is full");}} - POP : Kiedy element jest usuwany z góry stosu, jest znany jako operacja POP. Stos jest zmniejszany o jeden, po każdej operacji pop. Jeśli na stosie nie pozostanie żaden element, a pop zostanie wykonany, to spowoduje to BRAK WARIANTU, co oznacza, że twój stos jest pusty. POP OPERATION - funkcje w C:
Biorąc pod uwagę stos jest zadeklarowany jakoint stack [5], top = -1;void pop(){int item;if (top >= 4){item = stack [top];top = top - 1;printf ("Number deleted is = %d", item) ;}else{printf (" Stack is empty");}}
Operacje w kolejce
Podstawowe operacje, które można wykonać w kolejce, to:
- Enqueue : Aby wstawić element do kolejki. Funkcja operacji wygładzania w C:
Kolejka jest zadeklarowana jakoint queue [5], Front = -1 and rear = -1;void add (){int item;if ( rear < 4){printf ("Enter the number") ;scan ("%d", & item) ;if (front == -1){front =0 ;rear =0 ;}else{rear = rear + 1;}queue [rear] = item ;}else{printf ("Queue is full") ;}} - Dequeue : Aby usunąć element z kolejki. Funkcja operacji przycinania w C:
Kolejka jest zadeklarowana jakoint queue [5], Front = -1 and rear = -1;void delete (){int item;if ( front ! = -1){item = queue [ front ] ;if (front == rear){front =-1 ;rear =-1 ;}else{front = front + 1;printf ("Number deleted is = %d", item) ;}}else{printf ("Queue is empty") ;}}
Aplikacje Stack
- Parsowanie w kompilatorze.
- Maszyna wirtualna Java.
- Cofnij w edytorze tekstu.
- Przycisk Wstecz w przeglądarce internetowej.
- Język PostScript dla drukarek.
- Implementowanie wywołań funkcji w kompilatorze.
Aplikacje kolejki
- Bufory danych
- Asynchroniczny transfer danych (plik IO, rury, gniazda).
- Przydział żądań na udostępnionym zasobie (drukarka, procesor).
- Analiza ruchu.
- Określ liczbę kas kasowych w supermarkecie.
Wniosek
Stack i Queue to liniowe struktury danych, które różnią się pod wieloma względami, takimi jak mechanizm pracy, struktura, implementacja, warianty, ale obie 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óra jest odzyskiwana za pomocą innych typów kolejki.
