تنفيذ الطابور وDeque

بنية بيانات الطابور

from collections import deque

queue = deque()

# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue)          # deque([10, 20, 30])

# Peek front
print('Front:', queue[0])       # 10

# Dequeue (remove from front)
print('Dequeued:', queue.popleft())  # 10
print('Queue after:', queue)         # deque([20, 30])

فئة Queue باستخدام deque

from collections import deque

class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, val):
        self._data.append(val)

    def dequeue(self):
        if self.is_empty():
            raise IndexError('dequeue from empty queue')
        return self._data.popleft()

    def peek(self):
        if self.is_empty():
            raise IndexError('peek at empty queue')
        return self._data[0]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek())     # 1
print(q.dequeue())  # 1
print(len(q))       # 2

BFS باستخدام طابور

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue   = deque([start])
    order   = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return order

graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0))  # [0, 1, 2, 3, 4, 5]

الطابور الدائري (LeetCode 622)

class MyCircularQueue:
    def __init__(self, k):
        self.data  = [0] * k
        self.head  = 0
        self.tail  = 0
        self.count = 0
        self.k     = k

    def enQueue(self, value):
        if self.isFull(): return False
        self.data[self.tail] = value
        self.tail  = (self.tail + 1) % self.k
        self.count += 1
        return True

    def deQueue(self):
        if self.isEmpty(): return False
        self.head  = (self.head + 1) % self.k
        self.count -= 1
        return True

    def Front(self):
        return -1 if self.isEmpty() else self.data[self.head]

    def Rear(self):
        return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]

    def isEmpty(self): return self.count == 0
    def isFull(self):  return self.count == self.k

cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3))  # True True True
print(cq.enQueue(4))   # False (full)
print(cq.Rear())       # 3
print(cq.isFull())     # True
print(cq.deQueue())    # True
print(cq.enQueue(4))   # True

أكبر عنصر في النافذة المنزلقة باستخدام deque رتيب

from collections import deque

def maxSlidingWindow(nums, k):
    dq     = deque()   # stores indices, decreasing values
    result = []
    for i, n in enumerate(nums):
        # Remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Remove smaller elements from back
        while dq and nums[dq[-1]] < n:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

لماذا نستخدم deque بدلًا من list للطابور؟

import timeit

n = 10000

# Using list (O(n) per popleft)
list_time = timeit.timeit(
    stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
    globals={'n': n}, number=10
)

# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
    stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
    globals={'n': n, 'deque': deque}, number=10
)

print(f'List:  {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')

اجتياز الشجرة الثنائية مستوىً تلو الآخر (LeetCode 102)

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right

def levelOrder(root):
    if not root:
        return []
    result = []
    queue  = deque([root])
    while queue:
        level      = []
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root))  # [[3], [9, 20], [15, 7]]

طابور الأولوية باستخدام heapq

import heapq

pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)

print('Min:', heapq.heappop(pq))  # 1
print('Min:', heapq.heappop(pq))  # 2
print('Min:', heapq.heappop(pq))  # 3

# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
    priority, task = heapq.heappop(tasks)
    print(f'Priority {priority}: {task}')

النمط التطبيقي: الطابور لمشكلة Word Ladder

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
    queue    = deque([(beginWord, 1)])
    visited  = {beginWord}
    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + ch + word[i+1:]
                if new_word == endWord:
                    return steps + 1
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, steps + 1))
    return 0

print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog']))  # 5

deque بوصفه طابورًا مزدوج الطرفين

from collections import deque

dq = deque([3, 4, 5])

dq.appendleft(2)   # add to front: [2,3,4,5]
dq.appendleft(1)   # add to front: [1,2,3,4,5]
dq.append(6)       # add to rear:  [1,2,3,4,5,6]

print(dq.popleft())  # 1 (from front)
print(dq.pop())      # 6 (from rear)
print(list(dq))      # [2, 3, 4, 5]

الخلاصة: الطابور مقابل deque مقابل heap

اختبار سريع

خلاصة الدرس