Struktury danych
„Właściwie uważam, że różnica pomiędzy złym i dobrym programistą zależy od tego, czy ważniejszy jest dla niego kod, czy struktury danych. Zły programista zwraca uwagę na kod. Dobry programista przejmuje się strukturami danych oraz ich wzajemnymi relacjami”.
— Linus Torvalds
Struktura danych to format używany do przechowywania i organizowania informacji. Struktury danych mają kluczowe znaczenie dla programowania i większość języków programowania dysponuje kilkoma wbudowanymi ich rodzajami. Już wiemy, jak używać kilku wbudowanych struktur danych dostępnych w języku Python, takich jak listy, krotki oraz słowniki. W tym rozdziale przedstawione zostaną sposoby tworzenia i stosowania dwóch dodatkowych struktur — stosów oraz kolejek.
Stosy
Stos (ang. stack) jest strukturą danych. Podobnie jak w przypadku list, także do stosów można dodawać elementy oraz je z nich usuwać. Jednak w odróżnieniu od list, element dodawany do
stosu umieszczany jest zawsze na jego końcu i usunąć ze stosu można tylko jego ostatni element. Z listy [1, 2, 3] możemy usunąć dowolny element. Kiedy jednak dysponujemy stosem o takiej
samej zawartości, możemy z niego usunąć wyłącznie element 3. Jeśli tak zrobimy, stos będzie mieć postać [1, 2]. W tym momencie będziemy mogli usunąć ze stosu element 2. Po usunięciu
elementu 2 ze stosu będziemy mogli usunąć element 1, co sprawi, że stos stanie się pusty. Gdy usuwamy element ze stosu, mówimy, że jest on zdejmowany. Jeśli do pustego stosu ponownie
dodamy element 1, stos przyjmie postać [1]. Jeśli dodamy do niego liczbę 2, przyjmie postać [1, 2]. W przypadku dodawania elementu do stosu mówimy, że jest zapisywany na stosie lub odkładany na stos. Struktura danych tego typu, w której ostatni zapisany element jest jednocześnie pierwszym, który zostanie z niej pobrany, jest nazywana strukturą „ostatni zapisany, pierwszy obsłużony” (ang. LIFO — Last In First Out).
Strukturę danych typu LIFO można porównać do stosu naczyń. Jeśli na takim stosie umieścimy pięć talerzy, to by dotrzeć do znajdującego się na samym dole, będziemy musieli zdjąć wszystkie
pozostałe. Wyobraźmy sobie zatem każdą daną zapisywaną na stosie jako talerz — aby dostać się do niej, musimy zdjąć ze stosu wszystkie dane umieszczone wyżej. W tym miejscu rozdziału zajmiemy się utworzeniem stosu. Python dysponuje biblioteką udostępniającą implementacje zarówno stosu, jak i kolejki, jednak opracowanie własnej implementacji pozwoli lepiej zrozumieć, jak działa ta struktura danych. Nasz stos będzie udostępniał pięć metod: is_empty, push, pop, peek oraz size. Pierwsza metoda is_empty będzie zwracać wartość True, jeśli stos będzie pusty, oraz wartość False w przeciwnym przypadku.
Metoda push będzie odkładać element na wierzchołek stosu. Z kolei metoda pop będzie usuwać i zwracać element z wierzchołka stosu. Metoda peek będzie zwracać element z wierzchołka stosu bez jego usuwania. I w końcu metoda size będzie zwracać liczbę całkowitą reprezentującą liczbę elementów zapisanych na stosie. Poniżej przedstawiona została implementacja stosu napisana w Pythonie:
2
3 class Stack:
4 def __init__(self):
5 self.items = []
6
7 def is_empty(self):
8 return self.items == []
9
10 def push(self, item):
11 self.items.append(item)
12
13 def pop(self):
14 return self.items.pop()
15
16 def peek(self):
17 last = len(self.items)-1
18 return self.items[last]
19
20 def size(self):
21 return len(self.items)
Nowy stos po utworzeniu będzie pusty, a wywołanie jego metody is_empty zwróci True:
2
3 stack = Stack()
4 print(stack.is_empty())
>> True
Po dodaniu do stosu nowego elementu metoda is_empty zwróci wartość False:
2
3 stack = Stack()
4 stack.push(1)
5 print(stack.is_empty())
>> False
Jeśli wywołamy metodę pop, aby usunąć element ze stosu, metoda is_empty ponownie zwróci wartość True:
2
3 stack = Stack()
4 stack.push(1)
5 item = stack.pop()
6 print(item)
7 print(stack.is_empty())
>> 1
>> True
I w końcu możemy skorzystać z metody peek, aby podejrzeć element znajdujący się na wierzchołku stosu bez jego zdejmowania, oraz z metody size, by sprawdzić liczbę elementów umieszczonych na stosie:
2
3 stack = Stack()
4
5
6 for i in range(0, 6):
7 stack.push(i)
8
9
10 print(stack.peek())
11 print(stack.size())
>> 5
>> 6
Odwracanie łańcucha znaków przy użyciu stosu Korzystając ze stosu, można odwrócić kolejność, w jakiej jest zapisana zawartość danej iterowalnej, gdyż wszystko, co zostanie zapisane na stosie, jest z niego pobierane w odwrotnej kolejności. W tym podrozdziale rozwiążemy problem, który często pojawia się na rozmowach kwalifikacyjnych — odwracanie kolejności znaków w łańcuchu poprzez jego zapisanie na stosie i odczyt:
2
3 class Stack:
4 def __init__(self):
5 self.items = []
6
7 def is_empty(self):
8 return self.items == []
9
10 def push(self, item):
11 self.items.append(item)
12
13 def pop(self):
14 return self.items.pop()
15
16 def peek(self):
17 last = len(self.items)-1
18 return self.items[last]
19
20 def size(self):
21 return len(self.items)
22
23
24 stack = Stack()
25 for c in "Witam":
26 stack.push(c)
27
28
29 reversed_string = ""
30
31
32 for i in range(len(stack.items)):
33 reversed_string += stack.pop()
34
35
36 print(reversed_string)
>> matiW
Najpierw kolejno przeglądamy wszystkie znaki łańcucha "Witam" i zapisujemy je na stosie. Następnie pobieramy wszystkie elementy ze stosu, a każdy z nich dodajemy do zmiennej reverse.
Po zakończeniu iteracji początkowe słowo będzie zapisane w odwrotnej kolejności, a program wyświetli łańcuch matiW.
Kolejki
Kolejną strukturą danych jest kolejka (ang. queue). Także kolejki są podobne do list; pozwalają na dodawanie i usuwanie elementów. Co więcej, kolejki przypominają nieco stosy, gdyż elementy mogą być dodawane i usuwane z nich w ściśle określonej kolejności. Jednak w odróżnieniu od stosów, w których pierwszy element umieszczony na stosie jest jednocześnie ostatnim, który zostanie z niego pobrany, kolejki są strukturami danych „pierwszy zapisany, pierwszy obsłużony” (ang. FIFO — First In First Out) — pierwszy element zapisany w kolejce jest jednocześnie pierwszym, który zostanie z niej pobrany. Strukturę danych typu FIFO można sobie wyobrazić jako zwyczajną kolejkę osób czekających na kupno biletu do kina. Pierwsza osoba stojąca w tej kolejce jest jednocześnie pierwszą, która ten bilet kupi; druga osoba w kolejce kupi bilet jako druga w kolejności i tak dalej. W tym podrozdziale zaimplementujemy kolejkę udostępniającą cztery metody: enqueue, dequeue, is_empty oraz size. Pierwsza z tych metod, czyli enqueue, będzie dodawać element do kolejki, a druga — dequeue — pobierać z niej element. Metoda is_empty będzie zwracać wartość True, jeśli kolejka będzie pusta, lub wartość False w przeciwnym przypadku. Ostatnia metoda, size, będzie zwracać liczbę elementów zapisanych w kolejce.
2
3
4 class Queue:
5 def __init__(self):
6 self.items = []
7
8 def is_empty(self):
9 return self.items == []
10
11 def enqueue(self, item):
12 self.items.insert(0, item)
13
14 def dequeue(self):
15 return self.items.pop()
16
17 def size(self):
18 return len(self.items)
Bezpośrednio po utworzeniu kolejka jest pusta, zatem wywołanie metody is_empty zwróci True:
2
3 a_queue = Queue()
4 print(a_queue.is_empty())
>> True
Dodajmy teraz do kolejki kilka elementów i sprawdźmy jej wielkość:
2
3 a_queue = Queue()
4
5 for i in range(5):
6 a_queue.enqueue(i)
7
8 print(a_queue.size())
>> 5
Kolejny przykład pokazuje usuwanie elementów z kolejki:
2
3 a_queue = Queue()
4
5 for i in range(5):
6 a_queue.enqueue(i)
7
8 for i in range(5):
9 print(a_queue.dequeue())
10
11 print()
12
13 print(a_queue.size())
>> 0
>> 1
>> 2
>> 3
>> 4
>>
>> 0
Kolejka po bilety
Kolejka może symulować grupę osób pragnących kupić bilet do kina:
2
3 import time
4 import random
5
6
7 class Queue:
8 def __init__(self):
9 self.items = []
10
11 def is_empty(self):
12 return self.items == []
13
14 def enqueue(self, item):
15 self.items.insert(0, item)
16
17 def dequeue(self):
18 return self.items.pop()
20 def size(self):
21 return len(self.items)
22
23 def simulate_line(self, till_show, max_time):
24 pq = Queue()
25 tix_sold = []
26
27 for i in range(10):
28 pq.enqueue("osoba_nr." + str(i))
29
30 t_end = time.time() + till_show
31 now = time.time()
32 while now < t_end and not pq.is_empty():
33 now = time.time()
34 r = random.randint(0, max_time)
35 time.sleep(r)
36 person = pq.dequeue()
37 print(person)
38 tix_sold.append(person)
39
40 return tix_sold
41
42 queue = Queue()
43 sold = queue.simulate_line(5, 1)
44 print(sold)
>> osoba_nr.0
>> osoba_nr.1
...
>>> ['osoba_nr.0', 'osoba_nr.1', 'osoba_nr.2', 'osoba_nr.3', 'osoba_nr.4', 'osoba_nr.5', 'osoba_nr.6', 'osoba_nr.7']
Na początek utworzyliśmy funkcję o nazwie simulate_line, symulującą sprzedaż biletów grupie osób ustawionych w kolejce. Funkcja ta ma dwa parametry — till_show oraz max_time. Pierwszy z tych parametrów jest liczbą całkowitą określającą liczbę sekund pozostałych do rozpoczęcia seansu, kiedy to nie będzie już czasu na kupowanie biletów. Drugi parametr także jest liczbą całkowitą i określa maksymalny czas (mierzony w sekundach), jaki zajmuje kupienie biletu. Wewnątrz funkcji tworzymy nową, pustą kolejkę oraz pustą listę. Na liście będą umieszczane osoby, które już kupiły bilet. Następnie w kolejce zapisywanych jest 100 łańcuchów znaków, zaczynając od "osoba_nr.0", a kończąc na "osoba_nr.99". Każdy z tych łańcuchów znaków reprezentuje jedną osobę stojącą w kolejce po bilety. Wbudowany moduł time zawiera funkcję o nazwie time. Zwraca ona liczbę zmiennoprzecinkową reprezentującą liczbę sekund, które upłynęły od epoki — wyznaczonej daty (1 stycznia 1970 roku) używanej jako punkt odniesienia. Jeśli teraz wywołamy tę funkcję, zwróci ona wartość 1504001334.639 — liczbę sekund, które upłynęły od epoki. Gdybyśmy wywołali tę funkcję ponownie po upłynięciu 1 sekundy, zwrócona wartość zostałaby powiększona o 1. Następnie w zmiennej t_end zapisujemy wynik zwrócony przez funkcję time powiększony o liczbę sekund przekazaną jako parametr till_show. Wartość ta wyznacza punkt w przyszłości.
Pętla while umieszczona w dalszej części funkcji jest wykonywana do momentu, gdy funkcja time zwróci wartość większą od t_end bądź też do momentu, gdy kolejka zostanie opróżniona. Wewnątrz tej pętli używamy funkcji sleep należącej do wbudowanego modułu time, aby wstrzymać wykonywanie programu na pewną liczbę sekund, wybraną losowo z zakresu od 0 do max_time. To wstrzymanie wykonywania kodu ma symulować czas, jaki zajmuje kupienie biletu. Czas, na jaki działanie programu zostanie wstrzymane, jest losowy, aby zasymulować fakt, że czas potrzebny do sprzedania biletu może być różny.
Po przerwie spowodowanej wywołaniem funkcji sleep usuwamy z kolejki łańcuch reprezentujący osobę i umieszczamy go na liście tix_sold. Operacja ta reprezentuje sprzedanie biletu danej osobie. W ten sposób zaimplementowaliśmy funkcję symulującą sprzedawanie biletów kolejce osób. Liczba sprzedanych biletów jest zależna od przekazanych parametrów, jak również od losowo generowanych liczb.
Słownictwo
Epoka. Wyznaczony moment czasu używany jako punkt odniesienia.
FIFO. Pierwszy zapisany, pierwszy obsłużony.
Kolejka. Struktura danych typu FIFO.
LIFO. Ostatni zapisany, pierwszy obsłużony.
Odkładanie. Dodawanie elementów do stosu.
Stos. Struktura danych typu LIFO.
Struktura danych ostatni zapisany, pierwszy obsłużony. Struktura danych, w której ostatni element zapisany w strukturze jest jednocześnie pierwszym, który zostanie z niej usunięty.
Struktura danych pierwszy zapisany, pierwszy obsłużony. Struktura danych, w której pierwszy element zapisany w strukturze jest jednocześnie pierwszym, który zostanie z niej usunięty.
Struktura danych. Format używany do przechowywania i organizowania informacji.
Zdejmowanie. Usuwanie elementów ze stosu.
