6.1 Stekin tərifi və onun xassələri
Stek — bu abstrakt data strukturu olub, elementlərdən ibarət kolleksiyadır və "son daxil olan — birinci çıxır" prinsipi ilə (Last In, First Out, LIFO) təşkil olunur. Steki kitab dəstəsi kimi təsəvvür etmək olar: son əlavə olunan kitab dəstənin üstünə qoyulur və ilk götürüləcək.
Stekin xassələri:
- LIFO (Last In, First Out): Ən son əlavə olunan element birinci çıxarılır.
- Məhdud əməliyyatlar: Stekdə yalnız əlavə etmə (push), silmə (pop) və üzərinə baxış (peek) əməliyyatları dəstəklənir.
- Tək istiqamətdə giriş: Elementlərə yalnız stekin üzərindən giriş mümkündür.
- Sadə realizasiya: Steki massiv və ya əlaqəli siyahı istifadə edərək asanlıqla tətbiq etmək olar.
- Yaddaşın idarə olunması: Müvəqqəti verilənlər və ya vəziyyətlər onların əlavə edilmə sırasına tərs olaraq saxlanıla və bərpa edilə bilər.
LIFO prinsipi ilə iş:
- Elementin əlavə edilməsi (push): Yeni element stekin üstünə əlavə edilir.
- Elementin silinməsi (pop): Son daxil edilmiş element stekin üstündən silinir.
- Üzərinə baxış (peek): Stekin üstündəki elementə baxmağa imkan verir, amma onu silmir.
Stekin elementləri yalnız bir tərəfdən - "top" adlanan tərəfdən əlavə edilir və silinir. Beləliklə, son əlavə olunan element həmişə üstədir və ilk olaraq silinir.
6.2 Əsas əməliyyatlar
Əsas əməliyyatlar: push, pop, peek
Əməliyyat push: Yeni elementi stack-in üstünə əlavə edir.
Zaman mürəkkəbliyi: O(1).
Python-da list sinifindən istifadə edərək stack-in emulyasiyası nümunəsi:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # Çıxış: [10, 20]
Əməliyyat pop: Stack-in üstünə yerləşmiş elementi silir və geri qaytarır.
Zaman mürəkkəbliyi: O(1).
Python-da list sinifindən istifadə edərək stack-in emulyasiyası nümunəsi:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # Çıxış: 20
print(stack) # Çıxış: [10]
Əməliyyat peek: Stack-in üstünə yerləşmiş elementi silinmədən qaytarır.
Zaman mürəkkəbliyi: O(1).
Reallaşdırma nümunəsi:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # Çıxış: 10
6.3 Stack-dan istifadənin nümunələri
Gəlin stack-dan istifadənin bir neçə nümunəsini nəzərdən keçirək:
Funksiya çağırışlarının idarə olunması
Python-da stack proqramın icra prosesi zamanı funksiyaların izlənməsi üçün istifadə olunur. Hər dəfə bir funksiya çağırıldıqda, onun geri çağırış adresi və lokal dəyişənləri stack-a əlavə olunur. Funksiya icrasını başa çatdırdıqda, nəzarət onu çağıran funksiyaya qaytarılır və məlumatlar stack-dan çıxarılır.
Stack çağırışlarının istifadəsinə bir nümunə:
Bu nümunədə factorial funksiyasının rekursiv çağırışları hər bir çağırışın vəziyyətini saxlanması üçün stack çağırışlarından istifadə edir, əsas şərtə (n == 1) çatanda isə davam edir.
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # Çıxış: 120
Əməliyyatları geri almaq (Undo)
Stack, mətn redaktorlarında və digər tətbiqlərdə əməliyyatların geri alınması funksiyasını tətbiq etmək üçün istifadə olunur. İstifadəçi bir əməliyyat yerinə yetirdikdə, bu əməliyyat stack-a əlavə olunur. Undo əməliyyatı yerinə yetirildikdə, son əməliyyat stack-dan çıxarılır və geri alınır.
Əməliyyatların geri alınması üçün stack-dan istifadəyə nümunə:
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# İstifadə nümunəsi:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # Çıxış: "Hello World"
editor.undo()
print(editor.text) # Çıxış: "Hello"
editor.undo()
print(editor.text) # Çıxış: ""
GO TO FULL VERSION