Comparison

Stack (LIFO) vs Queue (FIFO) Definition

A stack follows the Last In, First Out (LIFO) principle. The most recently pushed element is the first one to be popped. Think of a stack of plates: you add and remove from the top.

A queue follows the First In, First Out (FIFO) principle. The first element added is the first one to be removed. Think of a line at a grocery store: the first person in line gets served first.

Side-by-Side Comparison

When to Use a Stack

• Undo/redo systems: Text editors push each action onto a stack and pop to undo.
• Function call management: The call stack tracks nested function calls and returns.
• Expression parsing: Converting infix to postfix notation uses operator stacks.
• Depth-first search: DFS explores as deep as possible before backtracking, which is natural for a stack.
• Browser history (back button): Visited pages are pushed onto a stack.
• Matching nested structures: Validating balanced parentheses requires LIFO matching.

When to Use a Queue

• Breadth-first search: BFS explores all neighbors before going deeper, which requires FIFO ordering.
• Task scheduling: CPU scheduling, print spoolers, and message queues process tasks in order.
• Buffering: Keyboard input buffering, streaming data buffers, and network packet queues.
• Producer-consumer systems: One thread produces data, another consumes it in order.
• Rate limiting: Track requests with timestamps in a queue and evict old ones.

When to Use Both (Deque)

Sometimes you need to add or remove from either end. A deque (double-ended queue) supports push_front, push_back, pop_front, and pop_back, all in O(1) time. Use a deque when the access pattern is not strictly LIFO or FIFO, or when you need a sliding window.

Implementing a Queue Using Two Stacks

This is a classic interview problem. The idea is to use one stack for enqueue and another for dequeue. When you dequeue and the output stack is empty, reverse the input stack into the output stack.

class QueueFromStacks:
    def __init__(self):
        self.inbox = []
        self.outbox = []

    def enqueue(self, x):
        self.inbox.append(x)

    def dequeue(self):
        self._shift()
        return self.outbox.pop()

    def peek(self):
        self._shift()
        return self.outbox[-1]

    def is_empty(self):
        return not self.inbox and not self.outbox

    def _shift(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

Each element is pushed and popped from each stack at most once, giving amortized O(1) time per operation.

Implementing a Stack Using Two Queues

This is less common but useful to know. The idea: enqueue the new element into an empty queue, then dequeue all elements from the other queue and enqueue them into the new queue. This makes the new element the front of the queue, effectively making it the "top" of the stack.

This approach has O(n) time per push because you must transfer all elements. There is no known O(1) amortized solution using two queues for stack operations.

Deque: The Best of Both Worlds

A deque (pronounced "deck") is a double-ended queue. It allows insertion and deletion at both ends in O(1) time. In Python, use collections.deque. In JavaScript, arrays can simulate a deque (but shift() is O(n) due to reindexing).

Use a deque when you need a sliding window, when both ends of the data are active, or when you are not sure whether LIFO or FIFO is the right pattern and want flexibility.

Decision Flowchart

Ask yourself these questions in order:

1. Do you need to process items in reverse order of arrival? If yes, use a stack.
2. Do you need to process items in order of arrival? If yes, use a queue.
3. Do you need to add and remove from both ends? If yes, use a deque.
4. Do you need to search or access elements in the middle? If yes, consider a list, set, or hash table instead.

When in doubt, start with the simplest structure that fits. You can always upgrade to a deque if you need more flexibility.