AlgoVerse

صف حلقوی

صفی روی یک آرایه‌ی با اندازه‌ی ثابت که وقتی به انتهای آرایه رسید، از ابتدا ادامه می‌دهد؛ هر درج و حذف O(1) است و جای خالی هدر نمی‌رود.

صف با آرایه‌ی ساده مشکلی دارد: با هر حذف از سر صف، جای خالی‌ای در ابتدای آرایه می‌ماند. در صف حلقوی آرایه را مثل حلقه در نظر می‌گیریم: بعد از آخرین خانه، اولین خانه می‌آید. پس:

ادامه‌ی توضیح ↓
ورودی:
n=10خروجی PDF

عددهای مثبت ENQUEUE و ۰ یعنی DEQUEUE؛ بعد از چند درج و حذف، rear از خانه‌ی ۴ به خانه‌ی ۰ دور می‌زند.

  1. def circular_queue(ops):
  2. # A positive number is enqueued; 0 dequeues. The queue lives in a fixed array of 5 slots.
  3. cap = 5
  4. buf = [None] * cap
  5. front = 0
  6. rear = 0
  7. size = 0
  8. out = []
  9. for op in ops:
  10. if op > 0:
  11. if size == cap:
  12. continue
  13. rear = (front + size) % cap
  14. buf[rear] = op
  15. size = size + 1
  16. else:
  17. if size == 0:
  18. continue
  19. out.append(buf[front])
  20. buf[front] = None
  21. front = (front + 1) % cap
  22. size = size - 1
  23. return out

ناوردا: عضوهای صف همیشه size خانه‌ی پشت سر هم از front به بعد هستند (با دور زدن به پیمانه‌ی ظرفیت).

شروع اجرا

100201302030440550660770809

متغیرهای محلی

نارنجی = در همین گام عوض شد

ops list

10203000405060700

Call stack

  1. circular_queue()خط 1
گام ۱ از ۷۲
خط سیاه = enqueue, dequeue · خط نارنجی = گام کلیدیenqueue: 0/7 · dequeue: 0/3
    توضیح

    ایده

    صف با آرایه‌ی ساده مشکلی دارد: با هر حذف از سر صف، جای خالی‌ای در ابتدای آرایه می‌ماند. در صف حلقوی آرایه را مثل حلقه در نظر می‌گیریم: بعد از آخرین خانه، اولین خانه می‌آید. پس:

    rear  = (front + size) mod cap
front = (front + 1) mod cap      (بعد از حذف)

    پر یا خالی؟

    اگر فقط front و rear را نگه داریم، front = rear هم می‌تواند یعنی پر و هم خالی. اینجا size را جدا نگه می‌داریم؛ کتاب هوروویتز یک خانه را همیشه خالی می‌گذارد تا این ابهام نباشد.

    ورودی

    عدد مثبت یعنی ENQUEUE همان عدد و 0 یعنی DEQUEUE. ظرفیت ۵ است.