A stos to liniowa struktura danych, która przechowuje elementy w pliku Ostatnie wejście/pierwsze wyjście (LIFO) lub metodą „pierwsze weszło/ostatnie wyszło” (FILO). W stosie nowy element jest dodawany na jednym końcu, a element jest usuwany tylko z tego końca. Operacje wstawiania i usuwania są często nazywane push i pop.

Funkcje powiązane ze stosem to:

• pusty() – Zwraca informację, czy stos jest pusty – Złożoność czasowa: O(1)
• rozmiar() – Zwraca rozmiar stosu – Złożoność czasowa: O(1)
• góra() / podgląd() – Zwraca referencję do najwyższego elementu stosu – Złożoność czasowa: O(1)
• pchnij(a) – Wstawia element „a” na górę stosu – Złożoność czasowa: O(1)
• Muzyka pop() – Usuwa najwyższy element stosu – Złożoność czasowa: O(1)

Realizacja:

Stos można zaimplementować w Pythonie na różne sposoby. W tym artykule omówiono implementację stosu przy użyciu struktur danych i modułów z biblioteki Python.
Stos w Pythonie można zaimplementować na następujące sposoby:

• lista
• Kolekcje.deque
• kolejka.LifoQueue

Implementacja za pomocą listy:

Wbudowanej w Pythona listy struktur danych można używać jako stosu. Zamiast push() append() służy do dodawania elementów na górę stosu, podczas gdy pop() usuwa element w kolejności LIFO.
Niestety lista ma kilka braków. Największym problemem jest to, że w miarę wzrostu mogą wystąpić problemy z szybkością. Pozycje na liście są przechowywane obok siebie w pamięci, jeśli stos urośnie większy niż blok pamięci, który go aktualnie przechowuje, Python będzie musiał dokonać alokacji pamięci. Może to prowadzić do tego, że niektóre wywołania funkcji append() będą trwały znacznie dłużej niż inne.

# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

Implementacja przy użyciu Collections.deque:

Stos Pythona można zaimplementować przy użyciu klasy deque z modułu kolekcji. Deque jest preferowany zamiast listy w przypadkach, gdy potrzebujemy szybszych operacji dołączania i pop z obu końców kontenera, ponieważ deque zapewnia złożoność czasową O(1) dla operacji dołączania i pop w porównaniu z listą, która zapewnia O(n) złożoność czasu.

Używane są te same metody deque, co na liście: append() i pop().

# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

Implementacja z wykorzystaniem modułu kolejkowego

Moduł kolejki ma również kolejkę LIFO, która jest w zasadzie stosem. Dane są wstawiane do kolejki za pomocą funkcji put(), a funkcja get() pobiera dane z kolejki.

W module tym dostępne są różne funkcje:

• największy rozmiar – Liczba pozycji dozwolonych w kolejce.
• pusty() – Zwraca True, jeśli kolejka jest pusta, w przeciwnym razie False.
• pełny() – Zwróć True, jeśli tak jest największy rozmiar pozycje w kolejce. Jeśli kolejka została zainicjowana wartością maxsize=0 (wartość domyślna), funkcja full() nigdy nie zwraca wartości True.
• Dostawać() – Usuń i zwróć element z kolejki. Jeśli kolejka jest pusta, poczekaj, aż pozycja będzie dostępna.
• get_nowait() – Zwróć przedmiot, jeśli jest natychmiast dostępny, w przeciwnym razie wyświetl QueueEmpty.
• umieścić (przedmiot) – Umieść przedmiot w kolejce. Jeśli kolejka jest pełna, poczekaj, aż zwolni się wolne miejsce, zanim dodasz przedmiot.
• put_nowait(przedmiot) – Umieść przedmiot w kolejce bez blokowania. Jeśli żadne wolne miejsce nie jest od razu dostępne, podnieś QueueFull.
• qrozmiar() – Zwraca liczbę pozycji w kolejce.

# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>

0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

Implementacja przy użyciu pojedynczo połączonej listy:

Połączona lista zawiera dwie metody addHead(item) i RemoveHead(), które działają w stałym czasie. Te dwie metody są odpowiednie do implementacji stosu.

• pobierzRozmiar() – Uzyskaj liczbę przedmiotów na stosie.
• jest pusty() – Zwraca True, jeśli stos jest pusty, False w przeciwnym razie.
• zerkać() – Zwróć najwyższy przedmiot ze stosu. Jeśli stos jest pusty, zgłoś wyjątek.
• naciśnij(wartość) – Wciśnij wartość na szczyt stosu.
• Muzyka pop() – Usuń i zwróć wartość z nagłówka stosu. Jeśli stos jest pusty, zgłoś wyjątek.

Poniżej implementacja powyższego podejścia:

# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # Uzyskaj bieżący rozmiar stosu def getSize(self): return self.size # Sprawdź, czy stos jest pusty def isEmpty(self): return self.size = = 0 # Zdobądź najwyższy element stosu def peek(self): # Kontrola sanitarna, aby zobaczyć, # czy podglądamy pusty stos. if self.isEmpty(): return Brak return self.head.next.value # Włóż wartość na stos. def push(self, wartość): węzeł = Węzeł(wartość) node.next = self.head.next # Ustaw nowy węzeł na bieżący nagłówek self.head.next = węzeł #!!! # Zaktualizuj głowę, aby była nowym węzłem self.size += 1 # Usuń wartość ze stosu i wróć. def pop(self): if self.isEmpty(): podnieś wyjątek('Wyskakuje z pustego stosu') usuń = self.head.next self.head.next = usuń.next #!!! zmieniony self.size -= 1 zwróć usuń.wartość # Kod sterownika if __name__ == '__main__': stos = Stack() dla i w zakresie (1, 11): stack.push(i) print(f' Stos: {stos}') dla _ w zakresie(1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # zmieniono nazwę zmiennej print(f'Stos: { stos}')>

Wyjście

Stack: 10->9->8->7->6->5->4->3->2->1 Pop: 10 Pop: 9 Pop: 8 Pop: 7 Pop: 6 Stos: 5->4->3->2->1>

Zalety stosu:

• Stosy to proste struktury danych z dobrze zdefiniowanym zestawem operacji, dzięki czemu są łatwe do zrozumienia i użycia.
• Stosy są wydajne przy dodawaniu i usuwaniu elementów, ponieważ operacje te mają złożoność czasową O (1).
• Aby odwrócić kolejność elementów stosujemy strukturę danych stosu.
• Stosy mogą służyć do implementowania funkcji cofania/ponawiania w aplikacjach.

Wady stosu:

• Ograniczenie rozmiaru stosu jest wadą i jeśli są one pełne, nie można już dodawać kolejnych elementów do stosu.
• Stosy nie zapewniają szybkiego dostępu do elementów innych niż element górny.
• Stosy nie wspierają wydajnego wyszukiwania, ponieważ musisz przeglądać elementy jeden po drugim, aż znajdziesz element, którego szukasz.