پشته ها (Stacks)
«پشته (Stack)» یک ساختار داده خطی است. قانونش LIFO است. یعنی «آخرین وارد، اولین خارج». مثل نان های روی هم؛ همیشه از بالا برمی داریم.
پشته چیست و چرا مهم است؟
پشته ظرفی برای عناصر است. عنصر تازه، بالای ظرف می نشیند. «پوش (Push)» یعنی افزودن بالا. «پاپ (Pop)» یعنی برداشتن از بالا. «پیک (Peek)» یعنی دیدن عنصر بالایی.
کاربردها زیادند: «واگردانی (Undo)»، تاریخچه مرورگر، و «پشته فراخوانی (Call Stack)». کنار پشته، «صف (Queue)» هم مهم است. ادامه را در صف ها ببین.
پیاده سازی با لیست پایتون
لیست پایتون همه نیازهای پشته را دارد. با append پوش می کنیم. با pop پاپ می کنیم.
stack = []
# Push
stack.append('A')
stack.append('B')
stack.append('C')
print("Stack:", stack)
# Peek
top_element = stack[-1]
print("Peek:", top_element)
# Pop
popped_element = stack.pop()
print("Pop:", popped_element)
# After Pop
print("Stack after Pop:", stack)
# isEmpty
is_empty = not bool(stack)
print("isEmpty:", is_empty)
# Size
print("Size:", len(stack))
نکته: لیست ها پویا هستند؛ اندازه شان رشد می کند. ولی دسترسی وسط، هزینه دارد.
پیاده سازی شیءگرا: کلاس Stack
کپسوله سازی یعنی مخفی کردن جزئیات. با کلاس «Stack» کار خواناتر می شود.
class Stack:
def __init__(self):
self._data = []
def push(self, element):
self._data.append(element)
def pop(self):
if self.is_empty():
return "Stack is empty"
return self._data.pop()
def peek(self):
if self.is_empty():
return "Stack is empty"
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def size(self):
return len(self._data)
my_stack = Stack()
my_stack.push('A')
my_stack.push('B')
my_stack.push('C')
print("Stack:", my_stack._data)
print("Pop:", my_stack.pop())
print("After Pop:", my_stack._data)
print("Peek:", my_stack.peek())
print("isEmpty:", my_stack.is_empty())
print("Size:", my_stack.size())
پیاده سازی با لیست پیوندی (Linked List)
«لیست پیوندی (Linked List)» از «گره (Node)» ساخته می شود. هر گره، داده و اشاره گر به بعدی دارد. افزودن و حذف سر، سریع است.
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
def __init__(self):
self.head = None
self._size = 0
def push(self, value):
new_node = Node(value)
if self.head:
new_node.next = self.head
self.head = new_node
self._size += 1
def pop(self):
if self.is_empty():
return "Stack is empty"
popped_node = self.head
self.head = self.head.next
self._size -= 1
return popped_node.value
def peek(self):
if self.is_empty():
return "Stack is empty"
return self.head.value
def is_empty(self):
return self._size == 0
def size(self):
return self._size
def traverse_and_print(self):
current = self.head
while current:
print(current.value, end=" -> ")
current = current.next
print()
stk = Stack()
stk.push('A')
stk.push('B')
stk.push('C')
print("LinkedList:", end=" ")
stk.traverse_and_print()
print("Peek:", stk.peek())
print("Pop:", stk.pop())
print("After Pop:", end=" ")
stk.traverse_and_print()
print("isEmpty:", stk.is_empty())
print("Size:", stk.size())
هشدار: لیست پیوندی حافظه بیشتری می خواهد. چون هر گره، اشاره گر هم دارد.
راهنمای انتخاب و گام های تمرین
اگر سادگی می خواهی، از لیست استفاده کن. اگر درج و حذف سریع در ابتدا می خواهی، لیست پیوندی خوب است.
- یک پشته با لیست بساز.
- همان را با کلاس پیاده سازی کن.
- سپس نسخه لیست پیوندی را تست کن.
برای مرور مفاهیم پایه لیست، صفحه لیست ها و آرایه ها را ببین.
جمع بندی سریع
- پشته یعنی LIFO؛ کار از بالاست.
- لیست پایتون، پوش و پاپ دارد.
- کلاس، کد را خواناتر می کند.
- لیست پیوندی، درج و حذف سر را سریع می کند.