صف ها (Queues)
«صف (Queue)» ساختار داده خطی با قانون FIFO است. یعنی «اولین وارد، اولین خارج». مثل صف بوفه مدرسه؛ نفر اول زودتر سرویس می گیرد.
صف چیست و چه عملیات هایی دارد؟
در صف، «انکیو (Enqueue)» افزودن عقب صف است. «دیکیُو (Dequeue)» برداشتن از جلوی صف است. «پیک (Peek)» عنصر جلویی را نشان می دهد. همچنین «خالی است؟» و «اندازه» را می سنجیم.
صف را می توان با «لیست (List)» یا «لیست پیوندی (Linked List)» ساخت. کاربردها زیادند؛ زمان بندی چاپگر و «جستجوی سطحی (BFS)» از نمونه ها هستند.
پیاده سازی صف با لیست پایتون
در لیست، افزودن آخر صف ساده است. اما حذف از ابتدا کند می شود؛ چون جابه جایی رخ می دهد.
queue = []
# Enqueue
queue.append('A')
queue.append('B')
queue.append('C')
print("Queue:", queue)
# Peek
front_element = queue[0]
print("Peek:", front_element)
# Dequeue
popped_element = queue.pop(0)
print("Dequeue:", popped_element)
print("Queue after Dequeue:", queue)
# isEmpty
is_empty = not bool(queue)
print("isEmpty:", is_empty)
# Size
print("Size:", len(queue))
نکته: برای صف های بزرگ، حذف از ابتدای لیست هزینه بر است.
پیاده سازی شیءگرا: کلاس Queue
با «کپسوله سازی (Encapsulation)» کد مرتب تر می شود. متدها واضح ترند.
class Queue:
def __init__(self):
self._data = []
def enqueue(self, element):
self._data.append(element)
def dequeue(self):
if self.is_empty():
return "Queue is empty"
return self._data.pop(0)
def peek(self):
if self.is_empty():
return "Queue is empty"
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def size(self):
return len(self._data)
q = Queue()
q.enqueue('A')
q.enqueue('B')
q.enqueue('C')
print("Queue:", q._data)
print("Peek:", q.peek())
print("Dequeue:", q.dequeue())
print("After Dequeue:", q._data)
print("isEmpty:", q.is_empty())
print("Size:", q.size())
صف با لیست پیوندی (Linked List)
در لیست پیوندی، هر «گره (Node)» داده و اشاره گر دارد. افزودن عقب و حذف جلو، بدون جابه جایی است.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
self._len = 0
def enqueue(self, element):
new_node = Node(element)
if self.rear is None:
self.front = new_node
self.rear = new_node
self._len += 1
return
self.rear.next = new_node
self.rear = new_node
self._len += 1
def dequeue(self):
if self.is_empty():
return "Queue is empty"
temp = self.front
self.front = temp.next
self._len -= 1
if self.front is None:
self.rear = None
return temp.data
def peek(self):
if self.is_empty():
return "Queue is empty"
return self.front.data
def is_empty(self):
return self._len == 0
def size(self):
return self._len
def print_queue(self):
temp = self.front
while temp:
print(temp.data, end=" -> ")
temp = temp.next
print()
q = Queue()
q.enqueue('A')
q.enqueue('B')
q.enqueue('C')
print("Queue:", end=" ")
q.print_queue()
print("Peek:", q.peek())
print("Dequeue:", q.dequeue())
print("After Dequeue:", end=" ")
q.print_queue()
print("isEmpty:", q.is_empty())
print("Size:", q.size())
هشدار: لیست پیوندی حافظه بیشتری می خواهد؛ چون هر گره اشاره گر دارد.
گام های تمرین و جمع بندی
- یک صف با لیست بساز.
- نسخه کلاس را پیاده سازی کن.
- مدل لیست پیوندی را تست کن.
برای مقایسه LIFO و FIFO، صفحه پشته ها را ببین. برای خود «لیست پیوندی»، به لیست های پیوندی سر بزن.
جمع بندی سریع
- صف یعنی FIFO؛ کار از جلو انجام می شود.
- لیست ساده است؛ ولی دیکیُو کند می شود.
- لیست پیوندی جابه جایی ندارد؛ اما حافظه می خواهد.
- کلاس Queue کد را مرتب و قابل توسعه می کند.