jaka jest podstawowa różnica między stosem a kolejką?

130

Jaka jest podstawowa różnica między stosem a kolejką?

Proszę, pomóż mi, nie mogę znaleźć różnicy.

Jak rozróżniasz stos i kolejkę?

Szukałem odpowiedzi w różnych linkach i znalazłem tę odpowiedź.

W programowaniu na wysokim poziomie

stos jest definiowany jako lista lub sekwencja elementów, która jest wydłużana poprzez umieszczanie nowych elementów „na wierzchu” istniejących elementów i skracana poprzez usuwanie elementów z góry istniejących elementów. Jest to ADT [Abstract Data Type] z operacjami matematycznymi „push” i „pop”.

Kolejka to sekwencja elementów, do których dodaje się poprzez umieszczenie nowego elementu z tyłu istniejącego i skraca się poprzez usunięcie elementów znajdujących się przed kolejką. Jest to ADT [Abstract Data Type]. W programowaniu w językach Java, C ++, Python i tak dalej można rozumieć te terminy.

Czy mogę otrzymać bardziej szczegółową odpowiedź? Proszę pomóż mi.

Harish Rachakonda
źródło
12
Wygląda na to, że odpowiedziałeś na swoje własne pytanie - stos to kontener Last-In First-Out (LIFO), a kolejka to kontener First-In First-Out (FIFO).
Iridium

Odpowiedzi:

153

Stos to struktura danych typu LIFO (ostatnie weszło, pierwsze wyszło). Powiązany link do wikipedii zawiera szczegółowy opis i przykłady.

Kolejka to struktura danych FIFO (pierwsze weszło, pierwsze wyszło). Powiązany link do wikipedii zawiera szczegółowy opis i przykłady.

jhonkola
źródło
133

Wyobraź sobie stos papieru . Ostatni element wrzucony do stosu znajduje się na górze, więc wychodzi jako pierwszy. To jest LIFO . Dodanie kartki papieru nazywa się „popychaniem”, a usunięcie kartki papieru - „wyskakiwaniem”.

Wyobraź sobie kolejkę w sklepie . Pierwsza osoba w kolejce jest pierwszą osobą, która z niej wychodzi. To jest FIFO . Osoba wchodząca w linię jest „kolejkowana”, a osoba wychodząca z linii jest „usuwana z kolejki”.

123
źródło
3
Jedna z najlepszych analogii, jakie przychodzą mi do głowy.
Yeikel
85

Model wizualny

Pancake Stack (LIFO)

Jedynym sposobem dodania i / lub usunięcia jednego jest od góry.

stos naleśników

Kolejka linii (FIFO)

Kiedy ktoś przybywa, dociera do końca kolejki, a kiedy ktoś wychodzi, wychodzi z przodu kolejki.

linia dmv

Ciekawostka: Brytyjczycy nazywają kolejki ludzi kolejką

Jacksonkr
źródło
6
Jezu, to musi być odpowiedź imo. Dzięki @Jacksonkr
Kulasangar
Haha, jestem pewien, że to doskonały opis Queue and Stack, ale dla samej argumentacji, co jeśli chcę, aby pierwszy naleśnik został dodany do talerza? Wiem, że można to uzupełnić za pomocą stack.size () vs. if (! Stack.isEmpty ()), ale nadal ten pierwszy naleśnik może być najlepszy :) ... Tak czy inaczej, fajna odpowiedź i zgadzam się, że to jest najjaśniejszy ... wydaje się interesujący, że Brytyjczycy nazywają linie kolejkami (jeśli to prawda), w języku nieprogramistycznym nadal uważałbym, że linia, w której pierwszy wpis wychodzi jako pierwszy (po wyjściu z linii / kolejki )
ViaTech
Czekaj, gdzie indziej nie nazywają się kolejkami?
wypad
37

Możesz myśleć o obu jako o uporządkowanej liście rzeczy (uporządkowanej według czasu, w którym zostały dodane do listy). Główna różnica między nimi polega na tym, w jaki sposób nowe elementy wchodzą na listę, a stare elementy opuszczają listę.

W przypadku stosu, jeśli mam listę a, b, ci dodam d, zostanie ona przypięta na końcu, więc kończę z a,b,c,d. Jeśli chcę zdjąć element listy, usuwam ostatni dodany element, czyli d. Po wyskakującym okienku moja lista jest teraz a,b,cznowu

W przypadku kolejki w ten sam sposób dodaję nowe elementy. a,b,cstaje się a,b,c,dpo dodaniu d. Ale teraz, kiedy wyskakuję, muszę wziąć element z początku listy i tak się stało b,c,d.

To jest bardzo proste!

cdesrosiers
źródło
14

Kolejka

Kolejka to uporządkowana kolekcja elementów.

Elementy są usuwane na jednym końcu zwanym „przednim” końcem kolejki.

Elementy są wstawiane na drugim końcu zwanym „tylnym” kolejki.

Pierwsza wstawiona pozycja jest pierwszą do usunięcia (FIFO).

Stos

Stos to zbiór przedmiotów.

Umożliwia dostęp tylko do jednej pozycji danych: ostatniej wstawionej pozycji.

Elementy są wstawiane i usuwane na jednym końcu zwanym „szczytem stosu”.

Jest to dynamiczny i ciągle zmieniający się obiekt.

Wszystkie elementy danych są umieszczane na szczycie stosu i zdejmowane z góry

Ta struktura dostępu jest znana jako struktura Last in First Out (LIFO)

Dissanayake
źródło
Zasadniczo więc „kolejka” to „FIFO” - pierwsza kolejka w pierwszej kolejności. Podczas gdy „stack” jest „LIFO” - ostatni w kolejce pierwszy na wyjściu. Mam rację?
Sebastian Nielsen
@SebastianNielsen Tak, jak podano w odpowiedzi.
Dissanayake
Jaka jest zatem różnica między listą połączoną a stosem? Czy to nie to samo?
Sebastian Nielsen
@SebastianNielsen Stos jest ADT, co oznacza, że ​​udostępnia interfejs, który jest operacją push i pop, ale podstawowy mechanizm (implementacja) jest ukryty przed użytkownikiem końcowym. Stos można zaimplementować za pomocą tablicy lub połączonej listy.
gdyrrahitis
13

STOS:

  1. Stos jest definiowany jako lista elementów, do których możemy wstawiać lub usuwać elementy tylko na samej górze stosu.
  2. Zachowanie stosu jest podobne do systemu Last-In First-Out (LIFO).
  3. Stos jest używany do przekazywania parametrów między funkcjami. W wywołaniu funkcji parametry i zmienne lokalne są przechowywane na stosie.
  4. Języki programowania wysokiego poziomu, takie jak Pascal, c, itp., Które zapewniają obsługę rekurencji, używają stosu do księgowania. Pamiętaj, że w każdym wywołaniu rekurencyjnym zachodzi potrzeba zapisania bieżącej wartości parametrów, zmiennych lokalnych oraz adresu zwrotnego (adresu, na który sterowanie ma powrócić po wywołaniu).

KOLEJKA:

  1. Kolejka to zbiór elementów tego samego typu. Jest to lista liniowy, w którym wstawki może odbywać się na końcu listy, zwane tylne z listy, a skreślenia może odbywać się tylko na drugim końcu, zwany przód listy
  2. Zachowanie kolejki jest podobne do systemu First-In-First-Out (FIFO).
ASHUTOSH KUMAR
źródło
Jestem prawie pewien, że możesz również wstawić na końcu lub na początku stosu, myślę, że ważną rzeczą do zapamiętania jest tutaj FIFO kontra LIFO
Mike
6

Stos to zbiór elementów, które można przechowywać i pobierać pojedynczo. Elementy są pobierane w kolejności odwrotnej do ich czasu przechowywania, tj. Ostatni zapisany element jest następnym pobieranym elementem. Stos jest czasami nazywany strukturą Last-In-First-Out (LIFO) lub First-In-Last-Out (FILO). Nie można pobrać wcześniej zapisanych elementów, dopóki nie zostanie pobrany najnowszy element (zwykle nazywany elementem „górnym”).

Kolejka to zbiór elementów, które można przechowywać i pobierać pojedynczo. Elementy są wyszukiwane według czasu ich przechowywania, tzn. Pierwszy zapisany element jest następnym pobieranym elementem. Kolejka jest czasami nazywana strukturą First-In-First-Out (FIFO) lub Last-In-Last-Out (LILO). Elementy przechowywane później nie mogą być odzyskane, dopóki nie zostanie pobrany pierwszy element (zwykle nazywany elementem „frontowym”).

Saurabh RS
źródło
2

STOS: Stos jest zdefiniowany jako lista elementów, do których możemy wstawiać lub usuwać elementy tylko na samej górze stosu

Stos jest używany do przekazywania parametrów między funkcjami. W wywołaniu funkcji parametry i zmienne lokalne są przechowywane na stosie.

Stos to zbiór elementów, które można przechowywać i pobierać pojedynczo. Elementy są pobierane w kolejności odwrotnej do ich czasu przechowywania, tj. Ostatni zapisany element jest następnym pobieranym elementem. Stos jest czasami nazywany strukturą Last-In-First-Out (LIFO) lub First-In-Last-Out (FILO). Nie można pobrać wcześniej zapisanych elementów, dopóki nie zostanie pobrany najnowszy element (zwykle nazywany elementem „górnym”).

KOLEJKA:

Kolejka to zbiór elementów tego samego typu. Jest to lista liniowa, w której wstawienia mogą mieć miejsce na jednym końcu listy, nazywanym końcem listy, a usunięcia mogą mieć miejsce tylko na drugim końcu, zwanym przodem listy

Kolejka to zbiór elementów, które można przechowywać i pobierać pojedynczo. Elementy są wyszukiwane według czasu ich przechowywania, tzn. Pierwszy zapisany element jest następnym pobieranym elementem. Kolejka jest czasami nazywana strukturą First-In-First-Out (FIFO) lub Last-In-Last-Out (LILO). Elementy przechowywane później nie mogą być odzyskane, dopóki nie zostanie pobrany pierwszy element (zwykle nazywany elementem „frontowym”).

shashimani
źródło
2

Aby spróbować nadmiernie uprościć opis stosu i kolejki, oba są dynamicznymi łańcuchami elementów informacyjnych, do których można uzyskać dostęp z jednego końca łańcucha, a jedyną prawdziwą różnicą między nimi jest fakt, że:

podczas pracy ze stosem

  • wstawiasz elementy na jednym końcu łańcucha i
  • pobierasz i / lub usuwasz elementy z tego samego końca łańcucha

będąc w kolejce

  • wstawiasz elementy na jednym końcu łańcucha i
  • pobierasz / usuwasz je z drugiego końca

UWAGA : Używam abstrakcyjnego sformułowania pobierania / usuwania w tym kontekście, ponieważ zdarzają się przypadki, gdy po prostu pobierasz element z łańcucha lub w pewnym sensie po prostu go czytasz lub uzyskujesz dostęp do jego wartości, ale są również przypadki, gdy usuwasz element z łańcuch i wreszcie są przypadki, gdy wykonujesz obie akcje tym samym wywołaniem.

Również element słowo jest celowo używany w celu jak największej abstrakcji wyimaginowanego łańcucha i oddzielenia go od określonych terminów języka programowania. Ta abstrakcyjna encja informacyjna zwana elementem może być czymkolwiek, od wskaźnika, wartości, ciągu lub znaków, obiektu ... w zależności od języka.

W większości przypadków jest to jednak wartość lub lokalizacja w pamięci (tj. Wskaźnik). A reszta po prostu ukrywa ten fakt za żargonem językowym <

Kolejka może być pomocna, gdy kolejność elementów jest ważna i musi być dokładnie taka sama, jak wtedy, gdy elementy pojawiły się w programie po raz pierwszy. Na przykład podczas przetwarzania strumienia audio lub podczas buforowania danych sieciowych. Lub gdy wykonujesz dowolny rodzaj przechowywania i przetwarzania dalej. We wszystkich tych przypadkach potrzeba, aby sekwencja elementów była wyświetlana w tej samej kolejności, w jakiej pojawiły się w programie, w przeciwnym razie informacja może przestać mieć sens. Możesz więc podzielić swój program na część, która odczytuje dane z niektórych danych wejściowych, wykonuje pewne przetwarzanie i zapisuje je w kolejce, a część, która pobiera dane z kolejki, przetwarza je i przechowuje w innej kolejce w celu dalszego przetwarzania lub przesyłania danych .

Stos może być pomocny, gdy potrzebujesz tymczasowo przechowywać element, który będzie używany w bezpośrednich krokach programu. Na przykład języki programowania zwykle używają struktury stosu do przekazywania zmiennych do funkcji. W rzeczywistości przechowują (lub wypychają) argumenty funkcji na stosie, a następnie przechodzą do funkcji, w której usuwają i pobierają (lub zdejmują) taką samą liczbę elementów ze stosu. W ten sposób rozmiar stosu zależy od liczby zagnieżdżonych wywołań funkcji. Dodatkowo, po wywołaniu funkcji i zakończeniu tego, co robiła, pozostawia ona stos w dokładnie takim samym stanie, jak przed wywołaniem! W ten sposób każda funkcja może działać ze stosem, ignorując sposób, w jaki inne funkcje z nim działają.

Na koniec powinieneś wiedzieć, że istnieją inne terminy używane dla tych samych lub podobnych pojęć. Na przykład stos można nazwać stertą. Istnieją również hybrydowe wersje tych koncepcji, na przykład podwójna kolejka może zachowywać się jednocześnie jako stos i kolejka, ponieważ oba końce mają do niej dostęp jednocześnie. Ponadto fakt, że struktura danych jest dostarczana jako stos lub jako kolejka, niekoniecznie oznacza, że ​​jest zaimplementowana jako taka, istnieją przypadki, w których struktura danych może być zaimplementowana jako dowolna i dostarczona jako określona struktura danych po prostu dlatego, że można ją tak zachowywać. Innymi słowy, jeśli zastosujesz metodę push and pop do dowolnej struktury danych, magicznie staną się one stosami!

Angelos Asonitis
źródło
Nie używaj formatowania kodu dla tekstu, który nie jest kodem.
Markiz Lorne
1

STACK to lista LIFO (ostatni na wejściu, pierwszy na wyjściu). oznacza, że ​​zakładamy, że 3 elementy są wstawione w stos, tj. 10,20,30. 10 jest wstawiane jako pierwsze, a 30 jest wstawiane jako ostatnie, więc 30 jest najpierw usuwane ze stosu, a 10 jest ostatnio usuwane ze stosu. To jest lista LIFO (Last In First Out).

KOLEJKA jest listą FIFO (First In First Out). Oznacza, że ​​jeden element jest wstawiany jako pierwszy, który ma zostać usunięty jako pierwszy. Np. Kolejka osób.

apurva sanjay borse
źródło
1

Układa uważaną kolekcję pionową. Najpierw zrozum, że kolekcja to OBIEKT, który gromadzi i organizuje inne mniejsze OBIEKTY. Te mniejsze OBIEKTY są powszechnie nazywane elementami. Te elementy są „odkładane” na stosie w kolejności ABC, gdzie A jest pierwszy, a C ostatni. w pionie wyglądałoby to tak: dodany trzeci element) C dodany drugi element) B dodany pierwszy element) A

Zauważ, że litera „A”, która jako pierwsza została dodana do stosu, znajduje się na dole. Jeśli chcesz usunąć „A” ze stosu, musisz najpierw usunąć „C”, następnie „B”, a na końcu element docelowy „A”. Stos wymaga podejścia LIFO podczas radzenia sobie ze złożonością stosu. (Last In First Out) Podczas usuwania elementu ze stosu poprawną składnią jest pop. nie usuwamy elementu ze stosu, usuwamy go.

Przypomnij sobie, że „A” był pierwszym elementem umieszczonym na stosie, a „C” ostatnim elementem odłożonym na stosie. Jeśli zdecydujesz, że chcesz zobaczyć, co znajduje się na dole stosu, ponieważ 3 elementy znajdują się na stosie uporządkowanym A jako pierwszy B jest drugim, a C jest trzecim elementem, górny musiałby zostać zdjęty, a następnie drugi element dodany w celu wyświetlenia spodu stosu.

Zimmermen7
źródło
Sformatuj swoje pytanie, aby wyglądało lepiej i było bardziej czytelne.
Neeku