Data Strukturlarının növləri.Stack data strukturu (part 1)
Stack, əməliyyatların aparıldığı müəyyən bir nizama əməl edən xətti məlumat quruluşudur. Stack-də sıralama LIFO (last in first out) və ya FILO (first in last out) şəklində olur.Misal olaraq üst-üstə yığlmış kitabları düşünə bilərik.Əgər oxumaq üçün bir kitab götürənsək ən üstdə olanı yəni ən son qoyduğumuz kitabı götürəcəyik.
Stack-də LİFO prinsipi
Proqramlaşdırma baxımından bir elementi Stack- ə əlavə etmək “push” və bir elementin çıxarılması “pop” adlanır.
Göründüyü kimi ən son “3” daxil olub və ilk çıxan elementdə “3”-dur. Bu da Stack-in LİFO prinsipinə uyğun gəldiyini göstərir.
Stack-in əsas əməliyyatları
Stack-də aşağıdakı əməliyyatları etmək mümkündür :
• Push: Stack-in üstünə bir element əlavə edir.
• Pop: bir Stack-də yuxarıdan bir element çıxarır.
• IsEmpty: Stack-in boş olub-olmadığını yoxlayır.
• IsFull: Stack-in dolu olub-olmadığını yoxlayır.
• Peek or Top : Stack-in ən üst elementini göstərir
Stack-dən istifadə
Bİz Stack class-ı yarada və stack məlumatlarını saxlamaq üçün Python-da olan “List”-dən (Array) istifadə edə bilərik. Bu class push, pop, size, top və is_empty metodlarınına sahib olacaqdır.
İlk addım bir class yaratmaq və burada məlumatlarımızı necə saxlayacağımızı bildirməkdir.
class Stack:
def __init__(self):
self.items = []Burada class və constructor yaratdıq.Constructor yarananda, dataları saxlamaq üçün boş bir array yaranacaqdır.
Push metodunda, yeni datalar əlavə etmək üçün “append” metodundan istifadə edirik.Bu zaman hər dəfə əlavə olunan yeni datamız array-mizin sonuncu index-inə yerləşəcəkdir.
def push(self, item):
self.items.append(item)Yeni məhsulu alır və siyahıya əlavə edir.
Ölçmə metodu (size method) yalnız len funksiyasından istifadə etməklə array-in uzunlugunu hesablayır.
def size(self):
return len(self.items)İs_empty metodunun məqsədi arraydə dataların olub-olmadığını yoxlamaqdır. Əgər varsa, False, əks halda True qaytarır. Array-də dataların sayını hesablamaq üçün, artıq tətbiq olunan ölçü metodundan(size method) istifadə edə bilərik.
def is_empty(self):
return self.size() == 0Pop metod , array-dən dataları silmək üçün istifadə edirik. Bu metoddan istifadə etdikdə ən sonuncu elementi silmis oluruq.
def pop(self):
return self.items.pop()Ancaq arrayin boş olması vəziyyətini də nəzərə almalıyıq. Boş bir array üçün pop metodu bir IndexError istisnasını(exception) göstərir. Beləliklə, bu məsələni həll etmək üçün bir istisna class-ı yarada bilərik.
class Emptiness(Exception):
passVə array boş olduğu halda bizə “Array boşdur” mesajını, əks halda isə silmə əməliyyatını yerinə yetirəcəkdir.
def pop(self):
if self.is_empty():
raise Emptiness('The Stack is empty')
return self.items.pop()Peek vəya Top metodu , arrayın ən sonuncu elementini bizə göstərir. Bu metod üçündə arrayən boş olun-olmaması vəziyyətindən yoxlaya bilərik :
def top(self):
if self.is_empty():
raise Emptiness('The Stack is empty')
return self.items[-1]Arraydə ən az bir data varsa onu bizə göstərəcəkdir.Əks halda arrayın boş olması halında bizə “Array boşdur” mesajını görəcəyik.
Stack class-ımızı yaratdıq və indidə ondan istifadə edək.
stack = Stack()
stack.is_empty() # True
stack.push(1) # [1]
stack.push(2) # [1, 2]
stack.push(3) # [1, 2, 3]
stack.push(4) # [1, 2, 3, 4]
stack.push(5) # [1, 2, 3, 4, 5]
stack.is_empty() # False
stack.top() # 5
stack.pop() # 5
stack.pop() # 4
stack.pop() # 3
stack.pop() # 2
stack.is_empty() # False
stack.pop() # 1
stack.is_empty() # True- İlk öncə Stack obyektini yaradırıq.
- is_empty metodu ilə boş olub-olmamasını yoxlayırıq.Və görürük ki boşdur.Çünki hələ heçbir data əlavə etməmişik.
- Push metodu ilə 5 dəfə data əlavə edirik.
- Yenidən is_empty ilə yoxlayırıq.Bu dəfə bizə “False” qaytarrır. Çünki artıq array-də datalarımız mövcuddur.
- top metodu dediyimiz kimi, bizə ən sonuncu datanı göstərir.Burada “5” olduğuna görə biz “5”-i görürük.
- pop metodu ilə 4 dəfə datanı silirik
- is_empty metodu ilə yoxlaıyıq və “True” alırıq çünki array-də bir dataımız mövcuddur.
- Daha sonra onuda silirik. Və yenidən is_empty etdikdə arrayimizin boş olduğunu görürük.
Mənbələr :
