DSA · Lesson 6 of 20 · 4 min
Stacks and Queues: LIFO & FIFO
Know these to explain browser history, the event loop, or solve backtracking problems.
Stacks and Queues are just arrays with rules. Instead of allowing access to any element, they restrict you to adding and removing elements from the ends. This constraint is their purpose. It simplifies logic for problems that involve processing items in a specific order.
In an interview, if a problem involves "the last thing I saw," "reversing order," or "backtracking," think Stack. If it's about "processing in order of arrival" or "first come, first served," think Queue.
Stacks: Last-In, First-Out (LIFO)
A stack follows the LIFO principle: the last element added is the first one to be removed. Think of the browser's call stack or a pile of plates. You add to the top and remove from the top.
The main operations are push (add to top) and pop (remove from top). You might also need peek (look at the top element without removing it).
When implemented with a dynamic array (like in JavaScript), all core stack operations are O(1). This is because you're only ever interacting with the end of the array, which doesn't require re-indexing the other elements.
class Stack<T> {
private storage: T[] = [];
// O(1)
push(item: T): void {
this.storage.push(item);
}
// O(1)
pop(): T | undefined {
return this.storage.pop();
}
// O(1)
peek(): T | undefined {
return this.storage[this.storage.length - 1];
}
// O(1)
isEmpty(): boolean {
return this.storage.length === 0;
}
// O(1)
size(): number {
return this.storage.length;
}
}
Queues: First-In, First-Out (FIFO)
A queue follows the FIFO principle: the first element added is the first one to be removed. This is a line at a checkout counter. You enqueue (add to the back) and dequeue (remove from the front).
This is where candidates get into trouble.
The trap: A naive queue implementation in JavaScript uses push to enqueue and shift to dequeue. While push is O(1), Array.prototype.shift() is an O(n) operation. To remove the first element, every other element in the array must be shifted one index to the left.
If you implement a queue using
shift(), a good interviewer will ask you about the time complexity ofdequeue. Your answer reveals whether you understand how JavaScript arrays work under the hood. For a small, fixed number of items, it's fine. For a queue that could grow, it’s a performance bottleneck.
A performant queue requires a different underlying structure. A Doubly Linked List is the textbook answer, as adding to the tail and removing from the head are both O(1) operations. Another option is a circular buffer or a simple two-pointer implementation over a fixed-size array, which avoids the O(n) re-indexing cost.
LIFO vs. FIFO Flow
The difference is which end you take from. Stacks are LIFO (add and remove from the same end). Queues are FIFO (add to one end, remove from the other).
Where You'll See Them in Frontend
These aren't just abstract algorithm concepts. They map directly to common frontend patterns.
Stacks are for nested or reversed contexts:
- Undo/Redo: User actions are
pushed onto anundostack. Hitting "undo"pops the last action andpushes it onto aredostack. - Browser History: Navigating to a new page
pushes the URL onto a session history stack. The back buttonpops from it. - Component Trees & Recursion: The call stack that manages function execution is a stack. When you render a tree of nested components, you are implicitly using the call stack to keep track of the parent-child hierarchy.
- Parsing: Validating balanced parentheses in a string is a classic stack problem. You
pushopening brackets andpopwhen you find a matching closer. This applies to validating nested HTML or JSX.
Queues are for ordered processing:
- The Event Loop: The browser's task queue is a queue. Events like user clicks,
setTimeoutcallbacks, and network responses are enqueued and processed in the order they were added. - State Updates: In some state management patterns, actions might be queued to be processed sequentially to prevent race conditions.
- Sequential Animations: If you need to run a series of animations one after another, you can
enqueuethem and have an animation managerdequeueand run the next one when the current one finishes.
Try it
Implement a function that uses a stack to check if a string of parentheses (), brackets [], and braces {} is balanced. This is the core of the classic Valid Parentheses problem. When you see an opening character, push it. When you see a closing one, pop and check if it's the matching opener.
Next: We'll look at solving problems with and without the call stack in Recursion and Iteration: Problem Solving Paradigms.
Lock it in — apply this lesson under interview conditions.