Stosy

https://docs.python.org/3/library/queue.html

WPROWADZENIE

Stos to ADT, który pozwala zapisywać dane i następnie pobierać je w kolejności odwrotnej do zapisu (ang. last in, first out, LIFO; ostatni wchodzi, pierwszy wychodzi). Interfejs stosu składa się minimum z czterech funkcji:

• Inicjalizacja pustego stosu (konstruktor).
• Test czy stos jest pusty (is_empty).
• Wstawienie elementu (push).
• Pobranie elementu (pop).
• Dostęp do ostatniego elementu stosu (top, peek).
• Odczyt liczby elementów na stosie (size).
• Czyszczenie stosu (clear).

Jeżeli stos ma ograniczenie na liczbę przechowywanych elementów, to stosuje się jeszcze funkcję is_full() [test czy stos jest pełny]. Czasem stosuje się jeszcze operację peek() lub top(), która daje dostęp do elementu na szczycie stosu, ale bez usuwania go ze stosu. Sytuacje prowadzące do błędu: przepełnienie stosu, pobieranie elementu z pustego stosu. Wydaje się, że nie jest ustalony jednolity sposób obsługi błędów. W Pythonie możemy zastosować mechanizm wyjątków lub zaimplementować inne rozsądne zachowanie (powiększenie stosu).

STOSY W PYTHONIE

Najprostsza realizacja stosu to zwykła lista Pythona i operacje append i pop.

Inna implementacja stosu może korzystać z collections.deque i operacji len, clear, append+pop lub appendleft+popleft.

#from Queue import LifoQueue   # Py2
from queue import LifoQueue   # Py3

S = LifoQueue()
# S.put(item)
# item = S.get()
# S.empty()   # czy pusta

IMPLEMENTACJA 1

Najpierw możemy wykorzystać standardowe listy Pythona do utworzenia stosu. Zastosujemy otoczkę obiektową wokół list. Python sam wykryje próbę pobierania danych z pustego stosu.

class Stack:

    def __init__(self):
        self.items = []

    def __str__(self):                  # podglądamy stos
        return str(self.items)

    def is_empty(self):
        return not self.items

    def is_full(self):                  # nigdy nie jest pełny
        return False

    def push(self, item):
        self.items.append(item)         # dodajemy na koniec

    def pop(self):                      # zwraca element
        return self.items.pop()         # zabieram od końca

Po zapisaniu kodu do osobnego modułu stack.py możemy w dowolnym programie korzystać z tego abstrakcyjnego typu danych. Python pozwala umieszczać na stosie elementy różnych typów bez dodatkowych zabiegów.

import stack

astack = stack.Stack()
for item in ["a", 2, 3.5]:
    astack.push(item)
# Zdejmowanie elementów ze stosu w kolejności 3.5, 2, "a".
while not astack.is_empty():
    print(astack.pop())

IMPLEMENTACJA 2

Implementacja stosu na bazie listy jednokierunkowej.

class Node:

    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

    def __str__(self):
        return str(self.data)

class Stack:

    def __init__(self):
        self.head = None

    def is_empty(self):
        return not self.head

    def is_full(self):
        return False

    def push(self, data):   # tak jak insert_head
        self.head = Node(data, next=self.head)

    def pop(self):   # tak jak remove_head
        if self.is_empty():
            raise Exception("stack is empty")
        data = self.head.data
        self.head = self.head.next
        return data

# Możemy skorzystać z przygotowanych wcześniej klas.
# Tutaj insert_head() i remove_head() używają 'node.data', a nie 'node'.
import slist

class Stack(slist.SingleList):
    # __init__ i is_empty są dziedziczone
    push = slist.SingleList.insert_head
    pop = slist.SingleList.remove_head

W implementacji z listą jednokierunkową operacje push() i pop() są klasy O(1) - czas pracy nie zależy od rozmiaru stosu. Pamięć zajmowana przez stos jest proporcjonalna do liczby przechowywanych elementów i nie ma ograniczenia na liczbę elementów.

IMPLEMENTACJA 3

Implementacja tablicowa stosu jest stosowana w językach programowania, które oferują tablice elementów jednego typu. Przy inicjalizacji stosu trzeba podać jego rozmiar, czyli maksymalną liczbę elementów, które ma przechowywać. Nowe elementy umieszczamy na coraz dalszych pozycjach w tablicy i zapamiętujemy liczbę elementów na stosie (jest to również indeks miejsca, do którego wstawimy następny element). Przy zdejmowaniu elementu ze stosu pomniejszamy numer indeksu, a na zwolnione miejsce wstawiamy bezpieczną wartość (w Pythonie jest nią 'None', a w C/C++ zero lub nullptr). W języku Python możemy łatwo zasymulować taką konstrukcję.

class Stack:

    def __init__(self, size=10):
        self.items = size * [None]      # utworzenie tablicy
        self.n = 0                      # liczba elementów na stosie
        self.size = size

    def is_empty(self):
        return self.n == 0

    def is_full(self):
        return self.size == self.n

    def push(self, data):
        self.items[self.n] = data
        self.n += 1

    def pop(self):
        self.n -= 1
        data = self.items[self.n]
        self.items[self.n] = None    # usuwam referencję
        return data

W implementacji tablicowej operacje push() i pop() są klasy O(1) - czas pracy nie zależy od rozmiaru stosu. Pamięć zajmowana przez stos jest stała i zależy od maksymalnej liczby elementów, które możemy trzymać na stosie.