یادداشت کامل الگوریتم

صف

Queue

Queue یا صف یک ساختمان داده FIFO است؛ یعنی اولین داده‌ای که وارد می‌شود، اولین داده‌ای است که خارج می‌شود.

نوعساختمان دادهدستهساختمان دادهسطحپایهپیچیدگی معمولenqueue/dequeue O(1)

جواب کوتاه و حرفه‌ای

اول این مفهوم را در ذهن نگه دار

Queue یا صف یک ساختمان داده FIFO است؛ یعنی اولین داده‌ای که وارد می‌شود، اولین داده‌ای است که خارج می‌شود.

توضیح ساده

چطور کار می‌کند؟ ساده و مرحله‌ای

داده‌ها از انتهای صف وارد و از ابتدای صف خارج می‌شوند.

وقتی ترتیب رسیدن کارها مهم است، Queue انتخاب طبیعی است.

روند اجرا

الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان

Invariant اصلی ساختار را مشخص کن.

مسیر read/update را در ساختار دنبال کن.

بعد از mutation قبل از return invariant را دوباره برقرار کن.

یک مثال کوچک برای فهم بهتر

اگر A و B و C را enqueue کنیم، اولین dequeue مقدار A را می‌دهد.

پیاده‌سازی خوانا با JavaScriptJavaScript

class Queue {
  #items = [];
  #head = 0;
  enqueue(value) { this.#items.push(value); }
  dequeue() {
    if (this.#head >= this.#items.length) return undefined;
    return this.#items[this.#head++];
  }
}

این کد را چطور بخوانی؟

syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.

پیچیدگی

enqueue/dequeue O(1)

این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.

چه زمانی استفاده کنیم؟

موارد مناسب

BFS
صف‌بندی کارها
Buffer کردن درخواست‌ها

اشتباهات رایج

کجا معمولاً اشتباه می‌کنیم؟

پیچیدگی را بدون فهم representation حفظ نکن.
بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.

در مصاحبه چطور توضیح بدهیم؟

مدل یک پاسخ حرفه‌ای

در مصاحبه FIFO را بگو و اشاره کن که برای Queue بزرگ در JavaScript بهتر است به‌جای shift مکرر از head index یا Deque استفاده کنیم.

مسئله→ایده اصلی→Invariant / State→Big-O→Trade-off

چند سؤال مصاحبه‌ای سریع

صف چه مسئله‌ای را حل می‌کند؟

Queue یا صف یک ساختمان داده FIFO است؛ یعنی اولین داده‌ای که وارد می‌شود، اولین داده‌ای است که خارج می‌شود.

درباره Complexity چه چیزی باید بگویم؟

پیچیدگی معمول اینجا enqueue/dequeue O(1) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.

رایج‌ترین اشتباه چیست؟

پیچیدگی را بدون فهم representation حفظ نکن.

موضوعات مرتبط برای ادامه مطالعهصف دو سرBFSصف اولویت

class Queue { #items = []; #head = 0; enqueue(value) { this.#items.push(value); } dequeue() { if (this.#head >= this.#items.length) return undefined; return this.#items[this.#head++]; } }