Stosy i kolejki oparte na tablicach vs listy

Istnieje wiele różnych sposobów implementacji kolejek i stosów z połączonymi listami i tablicami, i nie jestem pewien, których szukasz. Zanim jednak przeanalizujemy którąkolwiek z tych struktur, przejrzyjmy kilka ważnych kwestii związanych z uruchomieniem powyższych struktur danych.

W liście pojedynczo połączonej tylko ze wskaźnikiem głównym, koszt poprzedzania wartości wynosi O(1) - po prostu tworzymy nowy element, łączymy jego wskaźnik, aby wskazywał na starą głowicę listy, a następnie aktualizujemy głowicę pointer. Koszt usunięcia pierwszego elementu to również O(1), co odbywa się poprzez zaktualizowanie wskaźnika head, aby wskazywał na element za bieżącą głowicą, a następnie zwolnienie pamięci dla starej głowicy (jeśli wykonywane jest jawne zarządzanie pamięcią). Jednak stałe czynniki w tych warunkach O (1) mogą być wysokie ze względu na koszt dynamicznych alokacji. Narzut pamięci listy połączonej to zwykle O (N) całkowita dodatkowa pamięć ze względu na przechowywanie dodatkowego wskaźnika w każdym elemencie.

In a dynamiczna tablica, możemy uzyskać dostęp do dowolnego elementu w czasie O (1). Możemy również dodać element w o (1) , co oznacza, że całkowity czas dla N wstawek wynosi O (n), chociaż rzeczywiste granice czasu dla każdego Wstawienia mogą być znacznie gorsze. Zazwyczaj tablice dynamiczne są implementowane przez to, że większość wstawek zajmuje O(1), dołączając do wstępnie przydzielonej przestrzeni, ale mając niewielką liczbę wstawek uruchamianych w czasie Θ(n), podwajając pojemność tablicy i kopiując elementy. Istnieją techniki próbujące zmniejsz to, przydzielając dodatkową przestrzeń i leniwie kopiując elementy (patrz ta struktura danych , na przykład). Zazwyczaj użycie pamięci tablicy dynamicznej jest dość dobre - gdy tablica jest całkowicie Pełna, na przykład, jest tylko O(1) dodatkowy narzut - chociaż zaraz po podwojeniu rozmiaru tablicy mogą być O(n) nieużywane elementy przydzielone w tablicy. Ponieważ alokacje są rzadkie, a dostęp jest szybki, tablice dynamiczne są zwykle szybsze niż połączone listy.

Teraz zastanówmy się, jak zaimplementować stos i kolejkę za pomocą połączonej listy lub dynamicznej tablicy. Istnieje wiele sposobów, aby to zrobić, więc zakładam, że używasz następujących implementacji:

• stos:
  • Linked list: jako singly-linked list with a head pointer.
  • tablica: jako tablica dynamiczna
• Kolejka:
  • lista powiązana: jako lista pojedynczo powiązana z głową i ogonem pointer.
  • tablica: jako okrągły bufor wspierany przez tablicę.

Rozważmy każdy po kolei.

Stos wspierany przez pojedynczo połączoną listę. ponieważ lista pojedynczo-linkowana obsługuje o(1) time prepend and delete-first, koszt wepchnięcia lub wepchnięcia do stosu z linkowaną listą jest również o(1) worst-case. Jednak każdy nowy dodany element wymaga nowego przydziału, a alokacje mogą być kosztowne w porównaniu z innymi szef.

Stos wspierany przez tablicę dynamiczną. wciskanie na stos może być zaimplementowane przez dodanie nowego elementu do tablicy dynamicznej, co zajmuje czas o (1) i najgorszy O (n). Wyskakiwanie ze stosu można zaimplementować po prostu usuwając ostatni element, który działa w najgorszym przypadku O(1) (lub zamortyzowany O(1), jeśli chcesz spróbować odzyskać niewykorzystane miejsce). Innymi słowy, najczęściej spotykaną implementacją są best-case O (1) push i pop, worst-case O (n) push i O (1) pop, a amortyzowane O (1) push I O(1) pop.

Kolejka wspierana przez pojedynczo połączoną listę. zapytanie do listy linkowanej może być zaimplementowane przez dodanie na odwrocie listy linkowanej, co zajmuje najgorszy przypadek O (1). Dequeuing może być zaimplementowany przez usunięcie pierwszego elementu, co również zajmuje najgorszy czas O (1). Wymaga to również nowej alokacji na zapytanie, która może być powolna.

Kolejka wspierana przez rosnący okrągły bufor. zapytanie do bufor okrągły działa poprzez wstawienie czegoś w następnej wolnej pozycji w buforze okrągłym. Działa to poprzez zwiększenie tablicy w razie potrzeby, a następnie wstawienie nowego elementu. Korzystając z podobnej analizy dla tablicy dynamicznej, zajmuje to czas najlepszego przypadku O( 1), najgorszy czas O(n) i amortyzowany czas O(1). Usuwanie z bufora polega na usunięciu pierwszego elementu bufora kolistego, co w najgorszym przypadku zajmuje czas O(1).

Podsumowując, wszystkie konstrukcje wspierają pchanie i N elementów w czasie O (n). Wersje listy połączonej mają lepsze zachowanie w przypadku najgorszych przypadków, ale mogą mieć gorszy ogólny czas działania ze względu na liczbę wykonanych alokacji. Wersje tablic są wolniejsze w najgorszym przypadku, ale mają lepszą ogólną wydajność, jeśli czas na operację nie jest zbyt ważny.

Inną opcją, którą warto przyjrzeć się przy implementacji stosów, jest VList, ostatnia struktura danych, która jest hybrydą połączonej listy i dynamicznej tablicy. Informatyka robi mniej alokacji niż lista połączona i ma mniej wskaźników w nim, choć wykorzystanie przestrzeni jest nieco wyższe w najgorszym przypadku. Warto również przyjrzeć się chunklistom, które są kolejną hybrydą tablic i połączonych list, które mogą być używane zarówno dla stosów, jak i kolejek.

Mam nadzieję, że to pomoże!