Stack vs Queue vs Deque: Which Data Structure a Problem Wants

You pick a stack when elements must be processed in reverse order of arrival, a queue when order must be preserved strictly from front to back, and a deque when insertions and deletions happen at both ends. Most students waste interview time trying to fit every array problem into a hash map or sorting routine when the container choice alone determines whether the solution runs in O(n) time or times out.

Matching Brackets with a Stack

When an incoming element must be paired immediately with the most recent unmatched element, you need a stack. This last-in, first-out behavior matches problems where nesting matters.

Take the string {[()]}.

As you iterate through the characters, you push every opening bracket onto the stack. When you hit a closing bracket, you check the top of the stack. If it matches, you pop it. If it does not, the string is invalid.

Bool isValid(string s) {
    Stack<char> st;
    For (char c : s) {
        If (c == '(' || c == '{' || c == '[') {
            St.push(c);
        } else {
            If (st.empty()) return false;
            Char top = st.top();
            If ((c == ')' && top != '(') || 
                (c == '}' && top != '{') || 
                (c == ']' && top != '[')) return false;
            St.pop();
        }
    }
    Return st.empty();
}

The stack holds at most n characters, keeping space complexity proportional to the depth of the nesting rather than the total input size.

Breadth-First Search with a Queue

When a problem asks for the shortest path in an unweighted grid or tree, you use a queue. First-in, first-out order ensures you visit all nodes at distance k before visiting any node at distance k + 1.

Consider a binary tree where you want level-by-level traversal. You push the root node into the queue. Then you enter a loop where you pop the front node, read its value, and push its left and right children to the back.

If you used a stack here instead, you would end up doing a depth-first traversal and lose the shortest-path property entirely. The queue forces processing to spread outward uniformly in concentric layers from the source.

Sliding Window Maximum with a Deque

When a problem requires maintaining a moving window where elements can enter and leave from both ends efficiently, a deque is the right tool. A standard queue only lets you push to the back and pop from the front, which fails when you need to drop elements that fall out of bounds on the left while also purging smaller elements from the right.

Take the array [1, 3, -1, -3, 5, 3, 6, 7] with a window size of k = 3.

As the window slides across the array, the deque stores indices of elements rather than their values. Before adding a new element at index i, you pop indices from the back of the deque if their values are smaller than the current element. You also pop indices from the front if they are less than or equal to i - k. This keeps the maximum element at the front of the deque at all times.

Vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    Deque<int> dq;
    Vector<int> res;
    For (int i = 0; i < nums.size(); i++) {
        If (!dq.empty() && dq.front() <= i - k) {
            Dq.pop_front();
        }
        While (!dq.empty() && nums[dq.back()] <= nums[i]) {
            Dq.pop_back();
        }
        Dq.push_back(i);
        If (i >= k - 1) {
            Res.push_back(nums[dq.front()]);
        }
    }
    Return res;
}

Every element enters and leaves the deque at most once, which guarantees an O(n) runtime instead of the O(n * k) time you get from scanning every window with a nested loop.

Undo Operations and History

Problems involving text editors, browser history, or calculator state changes require tracking operations chronologically with the ability to step backward. A stack models this action naturally because the most recent operation is the first one you want to reverse.

When a user types a character, you push it onto an undo stack. When they press backstroke, you pop from the undo stack and push to a redo stack. The structure mirrors the physical reality of a stack of papers on a desk where you can only lift the top sheet.

The Container Selection Rule

Before writing any code, look at how data leaves the structure relative to how it enters.

• Last added leaves first: use a stack.
• First added leaves first: use a queue.
• Elements need removal from both ends based on index or value bounds: use a deque.

Open DSA Tracker today and sort your practice list by data structure type to solve five queue problems in a row without switching contexts.

Keep going with practice problems and the online compiler.

Further reading: Hash tables on Wikipedia.