Struktury danych: Stacks and Queues – Designveloper

Why Stacks and Queues?

W przeciwieństwie do tablicy, w stosach i kolejkach, nie ma operacji dostępu losowego (nie możemy uzyskać dostępu do elementu bezpośrednio za pomocą 'indeksu’). Zwykle mamy mniej metod/działań, które możemy wykonać, takich jak push(), pop(), peek(), enqueue(), dequeue(), z których wszystkie zajmują się wyłącznie elementem na początku lub końcu struktury danych.

Ale…

Pytanie: To brzmi tak ograniczająco, ponieważ możemy uzyskać dostęp tylko do pierwszego lub ostatniego elementu w strukturze danych. Dlaczego mielibyśmy kiedykolwiek chcieć używać czegoś takiego? Dlaczego po prostu nie użyjemy tablic dla większej elastyczności?

Odpowiedź: Stosy i kolejki są zazwyczaj „strukturami danych wyższego poziomu” zbudowanymi na wierzchu struktur niższego poziomu (tablica lub lista połączona), aby ograniczyć operacje, które możemy na nich wykonać. To jest korzyść, jeśli chcemy mieć ograniczony dostęp.

Mając tę ograniczoną zdolność na strukturze danych jest zaletą, ponieważ możemy kontrolować, kto używa tej struktury danych, która wykonuje tylko właściwe operacje, które są wydajne. Na przykład, nie będziemy musieli się zastanawiać, czy ktoś losowo wstawił element do środka naszej listy, psując niektóre inwarianty. Uratowało nas to przed wieloma problemami. Przyjrzyjmy się im dokładniej.

Czym jest stos?

Stos jest jednokońcową liniową strukturą danych, która modeluje rzeczywisty stos poprzez dwie podstawowe operacje, mianowicie push i pop.

Na poniższym obrazku widzimy, że jeden element danych jest usuwany z wierzchołka stosu, a drugi jest do niego dodawany. Istnieje wskaźnik górny wskazujący na blok na szczycie stosu. Dzieje się tak dlatego, że elementy w stosie zawsze są usuwane i dodawane na wierzchołek stosu. To zachowanie jest powszechnie znane jako LIFO (Last In First Out).

Operacje na stosie

Poniżej przedstawiono 2 podstawowe operacje, które można wykonać na stosie.

• Funkcja Push: Dodaj element na wierzchołek stosu
• Funkcja Pop: Usuń górny element (i może go zwrócić)

Wizualizacja podstawowych operacji stosu

Ponadto, dla stosu przewidziano następujące dodatkowe funkcje w celu sprawdzenia jego stanu.

• Funkcja Peek: Zwraca najwyższy element stosu bez jego usuwania lub kasowania
• Funkcja isEmpty: Sprawdź, czy stos jest pusty, czy nie
• Funkcja isFull: Sprawdź, czy stos jest pełny, czy nie

Wszystko operuje na wierzchołku stosu. Nie mamy dostępu do niczego innego poza wierzchołkiem. Jest to krytyczne w zrozumieniu, jak to działa.

Analiza złożoności

Poniższa tabela złożoności zakłada, że zaimplementowałeś stos za pomocą listy połączonej

Zastosowania stosów

Kiedy i gdzie jest używany stos? Używamy stosu w programowaniu, nawet tego nie zauważając, oto kilka przykładów:

• Może być używany do oceny wyrażeń (np.: algorytm shunting-yard do parsowania i oceny wyrażeń matematycznych).
• Może być używany do implementacji wywołań funkcji w programowaniu rekurencyjnym.

• Używany przez mechanizmy cofania w edytorach tekstu do cofania napisanego przez nas tekstu (Cmd + Z w Mac OS i Ctrl + Z w Windows)
• Używany w przeglądarce do nawigacji w tył i do przodu
• Może być używany do wyszukiwania w głąb (DFS) na grafie
• Używany za kulisami do obsługi rekurencji poprzez śledzenie poprzednich wywołań funkcji

Co to jest kolejka?

Kolejka jest również liniową strukturą danych, która modeluje kolejki świata rzeczywistego poprzez posiadanie dwóch podstawowych operacji, mianowicie enqueue (możemy myśleć o tym jako o „wejściu do kolejki”) i dequeue (możemy również myśleć o tym jako o „usunięciu z kolejki”). Struktura ta została nazwana „kolejką” ze względu na fakt, że przypomina prawdziwą kolejkę – (gdzie ludzie czekają w kolejce).

Każda kolejka ma przód i tył (czasami nazywany „tyłem”). Przez tył wstawiamy elementy, a przez przód je usuwamy.

Kolejka jest strukturą FIFO (First In First Out – element umieszczony jako pierwszy może być dostępny jako pierwszy), którą można powszechnie spotkać w wielu językach programowania.

Operacje kolejkowe

Poniżej przedstawiono 3 podstawowe operacje, które można wykonać na kolejce.

• Funkcja Enqueue: Dodaj element do końca kolejki
• Funkcja Dequeue: Usuń element z początku kolejki
• Funkcja Peeking: Podglądanie wartości z przodu kolejki bez jej usuwania

Analiza złożoności

Jak widzimy na obrazku, operacje enqueuing i dequeuing zajmują stały czas O(1). Jednak sprawdzenie, czy element jest zawarty w kolejce jest liniowo czasowe O(n), ponieważ potencjalnie musielibyśmy przeskanować wszystkie elementy.

Wewnętrznie istnieje również usuwanie elementów (nie dequeuing). Wymaga to czasu liniowego, ponieważ musimy przeskanować wszystkie elementy w najgorszym przypadku.

Zastosowania kolejek

• Używane do zarządzania wątkami w wielowątkowości.
• Może być używane do efektywnego śledzenia x ostatnio dodanych elementów
• Zarządzanie żądaniami serwera WWW, gdzie chcemy, aby pierwszeństwo było pierwsze. Na przykład: W danym momencie nasz serwer WWW może obsłużyć tylko maksymalnie 50 osób jednocześnie.

Jeśli w krótkim czasie przyjdzie 70 żądań, to nie będziemy w stanie obsłużyć ich wszystkich. Dlatego webserver wyskakuje z kolejki tylko 50 żądań, a pozostałe 20 wstrzymuje. Kiedy webserwer kończy przetwarzanie żądania, odkłada następne do obsłużenia i robi to tak długo, aż kolejka jest pusta.

• Breadth-first search (BFS) graph traversal
• Używane do implementacji systemów kolejkowania (np.: kolejki priorytetowe)
• Używane w drukarce sieciowej: Drukarka może obsłużyć tylko jedno żądanie w tym samym czasie. Jeśli więc przyjdą inne żądania, gdy drukarka jest zajęta, program zarządzający drukarką nie odrzuci tych żądań, ale umieści je w kolejce oczekujących na wykonanie. Pierwszy wniosek zostanie obsłużony jako pierwszy (FIFO).

Mamy nadzieję, że ten artykuł dał ci obraz stosów i kolejek w umyśle. Nie zapomnij zasubskrybować naszego bloga i śledzić Designvelopera na Facebooku, Twitterze i LinkedIn.

A oto inne artykuły, które mogą Ci się spodobać:

• Co to jest architektura aplikacji internetowych?
• Struktury danych i ich zastosowania
• Co to jest notacja Big O?

.