Pattern GuideStacks & Queues
Pricing
Core Data Structure

Stacks & Queues

"LIFO for recent backtracking tasks, FIFO for fair chronological processing."

7 min read
Fundamental Concept
True O(1) Ops
01
CORE INTUITION

Order Is the Clue

📚

The Rules of Order

Stacks and Queues aren't complex lookup arrays — they are access restrictors. They wrap a collection and force you to interact strictly with the ends.

Stack (LIFO - Last In First Out): Only touch the most recent item. Use this when a problem involves nesting, recursion, or backtracking — you need to undo, rewind, or match the newest thing first.

Queue (FIFO - First In First Out): Only touch the oldest item. Use this when a problem involves chronological scheduling, fairness, or level-by-level BFS expansion — you process things in the exact order they arrived.

02
STACKS

LIFO: Backtracking & Nesting

Every element is placed on the top of the stack. You can only remove from the top. This gives you access to only the most recent item.

Stack Trace Demo: Valid Parentheses Check on {[()]}

Scanning String Index
0
{
1
[
2
(
3
)
4
]
5
}
function isValid(s) {
let stack = []; // 1️⃣ Init
for (let i = 0; i < s.length; i++) {
let char = s[i]; // 2️⃣ Scan
if (char === '(' || char === '{' || char === '[') {
stack.push(char); // 3️⃣ Push
} else {
let top = stack.pop(); // 4️⃣ Pop
if (char === ')' && top !== '(') return false;
if (char === '}' && top !== '{') return false;
if (char === ']' && top !== '[') return false;
}
}
return stack.length === 0; // 5️⃣ End Check
}
Active Stack Tube
[ Empty Stack ]
Initialize an empty stack array to keep track of open brackets.

Strategy Blueprint

1️⃣
InitializeInitialize stack memory array to track components.
2️⃣
ScanIterate across elements, checking each char or item.
3️⃣
PushAdd open brackets or active states to the top of stack.
4️⃣
Pop / ComparePop top bracket when closing token matches, or fail if mismatched.
🎯 Target Scenario Signals:
Bracket NestingSequence ReversalBacktracking MazeMin Stack / extra bookkeeping

When the stack itself must stay sorted at all times (not just LIFO order) — see Monotonic Stack.

stack_operations.js
1
// A Stack uses an array inherently in JS
2
const stack = [];
3
4
// 1️⃣ Push element onto standard stack (LIFO)
5
stack.push(1);
6
stack.push(2);
7
8
// 2️⃣ Pop element off stack
9
const topElement = stack.pop(); // returns 2
10
11
// 3️⃣ Peek at top element safely
12
const top = stack.length > 0 ? stack[stack.length - 1] : null;
03
QUEUES

FIFO: Order & Chronological Fairness

New elements enter at the back (enqueue), and processed elements leave from the front (dequeue). This guarantees first-come, first-served chronological scheduling.

Queue Trace Demo: Process Tasks chronological queue

Active Queue Line
[Front] A
B
C
function processTasks(tasks) {
let queue = [...tasks]; // 1️⃣ Init
let processed = [];
while (queue.length > 0) {
let current = queue.shift(); // 2️⃣ Dequeue
processed.push(current); // 3️⃣ Execute
if (current === 'A') {
queue.push('A_sub'); // 4️⃣ Enqueue next
}
}
return processed;
}
Variables Monitor
current task:null
processed tasks:[]
Initialize queue buffer with root tasks ['A', 'B', 'C']. processed list starts empty.

Strategy Blueprint

1️⃣
InitializeInitialize queue memory array with entry tasks.
2️⃣
DequeueExtract the frontmost element queue.shift() (FIFO).
3️⃣
ExecuteProcess the active task and store it in output list.
4️⃣
Enqueue nextAdd newly discovered children or subtasks to the back of the queue.
🎯 Target Scenario Signals:
BFS TraversalFair Scheduler BufferData Streams
queue_operations.js
1
// Basic array Queue (O(N) dequeue due to shift)
2
const queue = [];
3
4
// 1️⃣ Enqueue element (FIFO)
5
queue.push(1);
6
queue.push(2);
7
8
// 2️⃣ Dequeue element (O(N) operation in JS!)
9
const frontObj = queue.shift();
10
11
// Tip: For O(1) dequeue in JS, utilize a custom Linked List.
04
BONUS

Deque: Both Ends

When One End Isn't Enough

A Deque (double-ended queue) allows O(1) insert and remove at both ends. It combines stack and queue access into one structure. The most common algorithmic use is maintaining a monotonic deque for sliding window maximum/minimum problems.

Key pattern: As the window slides, remove expired indices from the front and pop smaller values from the back. The front of the deque always holds the current window's maximum. See the Sliding Window guide for details.

05
PITFALLS

Common Mistakes

Underflow Errors

Attempting to pop or peek on an empty Stack/Queue. Always check !isEmpty() before retrieving values to avoid index out of bounds crashes.

Shift Complexity

Using array.shift() in JavaScript is O(N) due to index re-allocations. For true O(1) queues, use a Linked List or a specialized Deque implementation.

06
COMPLEXITY

Cheat Sheet

OperationStackQueue
Push / EnqueueO(1)O(1)
Pop / DequeueO(1)O(1) with a real queue — O(N) if backed by array.shift() (see Pitfalls)
PeekO(1)O(1)
07
PRACTICE

Ready to Practice?

Valid ParenthesesEasy
Simplify PathMedium
Evaluate Reverse Polish NotationMedium

"LIFO for the recent, FIFO for the fair."