پشته
StackStack یا پشته یک ساختمان داده LIFO است؛ یعنی آخرین چیزی که وارد می‌شود، اولین چیزی است که خارج می‌شود.
اول این مفهوم را در ذهن نگه دار
Stack یا پشته یک ساختمان داده LIFO است؛ یعنی آخرین چیزی که وارد می‌شود، اولین چیزی است که خارج می‌شود.
چطور کار می‌کند؟ ساده و مرحله‌ای
مثل یک دسته بشقاب فکر کن؛ اضافه‌کردن و برداشتن فقط از بالای پشته انجام می‌شود.
عملیات اصلی push، pop و peek هستند و در پیاده‌سازی مناسب معمولاً O(1) هستند.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
push مقدار را روی پشته می‌گذارد.
pop مقدار بالایی را حذف و برمی‌گرداند.
peek فقط مقدار بالایی را می‌خواند و حذف نمی‌کند.
اگر 1 و بعد 2 را push کنیم، pop مقدار 2 را برمی‌گرداند.
class Stack {
#items = [];
push(value) { this.#items.push(value); }
pop() { return this.#items.pop(); }
peek() { return this.#items.at(-1); }
get size() { return this.#items.length; }
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
push/pop O(1)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- Undo/Redo
- تحلیل expressionها
- DFS و Backtracking
کجا معمولاً اشتباه می‌کنیم؟
- pop روی پشته خالی را بدون تصمیم مشخص رها نکن.
- با shift ساختار را از انتهای مناسب Array دور نکن چون می‌تواند O(n) شود.
مدل یک پاسخ حرفه‌ای
اول LIFO را بگو، بعد push/pop/peek و یک مثال واقعی مثل call stack یا parsing را اضافه کن.
پشته چه مسئله‌ای را حل می‌کند؟
Stack یا پشته یک ساختمان داده LIFO است؛ یعنی آخرین چیزی که وارد می‌شود، اولین چیزی است که خارج می‌شود.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا push/pop O(1) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
pop روی پشته خالی را بدون تصمیم مشخص رها نکن.