Stacks and queues

In short

A stack is a linear ADT in which insertion and deletion happen at one end only (LIFO - last in, first out); a queue allows insertion at the rear and deletion at the front (FIFO - first in, first out). Both are "restricted-access" structures: the restriction is exactly what makes them O(1) per operation and what makes them the right model for recursion, expression parsing, scheduling and buffering. They are the most frequently examined data structures after arrays - GATE CS asks stack permutations, circular-queue index arithmetic and expression conversion almost every year, and placement rounds at TCS, Infosys, Wipro, Cognizant, Amazon, Microsoft, Flipkart, Zoho and Goldman Sachs routinely ask balanced parentheses, next greater element, min-stack and queue-using-two-stacks. In practice they sit inside every compiler, operating system, browser and message broker a student will ever work on.

Explained

The two ADTs: definition, operations and conditions

• Abstract data type (ADT): a specification of values and operations with no commitment to implementation. The stack and queue ADTs are defined by their access discipline, not by arrays or pointers.
• Stack operations: push(x) (insert at top), pop() (remove and return top), peek()/top() (read without removing), isEmpty(), isFull(), size(). All O(1).
• Stack axioms: pop(push(S, x)) = S and top(push(S, x)) = x - the defining LIFO property used in theory questions.
• Queue operations: enqueue(x) (insert at rear), dequeue() (remove from front), front(), rear(), isEmpty(), isFull(). All O(1).
• Underflow: popping/dequeuing an empty structure. Overflow: pushing/enqueuing a full fixed-size structure. Both must be checked *before* touching the array index - this is where most exam marks are lost.
• Neither structure supports random access or search in O(1); searching is O(n) and requires emptying the structure or an auxiliary one.

Implementations and their trade-offs

• Array (static) stack: top initialised to −1; push does A[++top] = x; pop does return A[top--]. Empty when top == −1, full when top == N−1. Contiguous, cache-friendly, but fixed capacity.
• Dynamic array stack: on overflow, allocate a new array of double the size and copy. Worst case for a single push is O(n), but amortised O(1) (derivation below). This is how C++ std::vector and Java's ArrayList/ArrayDeque-backed stacks grow; std::stack defaults to std::deque, which adds blocks instead of copying.
• Linked-list stack: push/pop at the head of a singly linked list - O(1) always, no fixed capacity, but 8-16 extra bytes per node for the pointer and poor locality.
• Linear array queue: front and rear both move forward only. After repeated enqueue-dequeue the queue "drifts" to the right and reports full while the front of the array is empty - the classic false overflow / wasted-space problem.
• Circular queue: indices wrap with modulo N, reusing freed slots. Two conventions:
  • *One slot sacrificed:* empty when front == rear, full when (rear+1) % N == front; maximum N−1 elements.
  • *Count variable:* store count; empty when count == 0, full when count == N; all N slots usable.
• Linked queue: keep both front and rear pointers; enqueue at rear, dequeue at front, both O(1). Dequeuing the last node must set both pointers to NULL.
• Two stacks in one array: stack 1 grows upward from index 0, stack 2 downward from N−1; overflow only when top1 + 1 == top2. Space-efficient when the two stacks' peak sizes are complementary.
• System (call) stack: the stack a program runs on. Each call pushes an activation record / stack frame holding parameters, return address, saved registers and locals; return pops it. Unbounded recursion causes stack overflow (typically 1-8 MB of stack per thread). Tail-recursive calls can be optimised into loops by some compilers; iterative conversion with an explicit stack always works.

Variants and classification

• Stack types: array-based (bounded), linked (unbounded), multi-stack in one array, min-stack / max-stack (O(1) extremum), monotonic stack (kept increasing or decreasing - the engine behind next-greater-element problems).
• Queue types:
  • *Simple (linear) queue* - FIFO, suffers false overflow.
  • *Circular queue* - wrap-around, no wasted slots.
  • *Deque (double-ended queue)* - insert and delete at both ends; addFront, addRear, deleteFront, deleteRear.
    • Input-restricted deque: insertion at one end only, deletion at both.
    • Output-restricted deque: insertion at both ends, deletion at one end only.
    • A deque can simulate both a stack and a queue, so it is the most general of the three.
  • *Priority queue* - dequeue by priority, not arrival order; normally built on a heap, and covered in its own note.
  • *Multiple queues / queue of queues* - used in multilevel feedback scheduling.
• Why a deque matters in interviews: sliding-window maximum, LRU cache ordering and 0-1 BFS all need O(1) access at both ends.

Stacks and expressions - the most examined application

• Notations: infix A + B, prefix (Polish) + A B, postfix (reverse Polish) A B +. Prefix and postfix need no parentheses and no precedence rules, which is why compilers and calculators use postfix.
• Precedence (highest first): ^ (3, right-associative), * / % (2, left-associative), + − (1, left-associative). Unary minus binds tighter than * and / but looser than ^, so −2^2 = −(2^2).
• Infix → postfix (shunting-yard), step by step:
  1. Scan left to right.
  2. Operand → append to output.
  3. ( → push.
  4. ) → pop and output until ( is popped and discarded.
  5. Operator *op* → while the stack top is an operator of higher precedence, or equal precedence and *op* is left-associative, pop it to output; then push *op*. (For right-associative ^, pop only on strictly higher precedence.)
  6. End of input → pop everything remaining to output.
• Infix → prefix: reverse the infix string, swap ( with ), convert to postfix treating ^ carefully, then reverse the result.
• Postfix evaluation: scan left to right; push operands; on an operator pop two values, apply as second_popped OP first_popped, push the result. The lone value left is the answer. Prefix evaluation is the same but scanned right to left with the operands applied in the opposite order.
• Balanced parentheses: push every opening bracket, and on a closing bracket check that the popped bracket is the matching type. Balanced iff no mismatch occurs and the stack is empty at the end.
• Other classical stack applications: reversing a string or a linked list, undo/redo (two stacks), browser back/forward (two stacks), DFS of a graph or tree, backtracking (N-queens, maze, Sudoku), stock span, largest rectangle in a histogram, checking well-formed HTML/XML tags, and converting any recursion into iteration.

Queues in systems, and the cross-conversions asked in interviews

• Scheduling: round-robin CPU scheduling is a circular queue of ready processes; disk I/O requests, print spooling and keyboard buffers are queues.
• Breadth-first search uses a queue and gives shortest paths in an unweighted graph; DFS uses a stack. Swapping the queue for a stack in the same code turns BFS into DFS.
• Producer-consumer / bounded buffer: a circular queue with synchronisation; the core of pipes, sockets, logging frameworks and message brokers (Kafka, RabbitMQ, Amazon SQS).
• Queue using two stacks: in and out. Enqueue pushes onto in. Dequeue pops from out; if out is empty, move everything from in to out first. Each element is pushed and popped at most twice → amortised O(1), worst case O(n) for a single dequeue.
• Stack using two queues: either make push O(n) (enqueue, then rotate all earlier elements behind it) or make pop O(n) (dequeue n−1 elements into the other queue). One operation must be O(n).
• Stack using one queue: push x, then dequeue-and-enqueue the preceding n−1 elements - push O(n), pop O(1).
• Min-stack in O(1): keep a parallel stack of minima, or store the encoded value 2x − min when a new minimum arrives and decode on pop (saves space, risks overflow on large values).
• Monotonic stack: maintain a stack whose values are strictly increasing (or decreasing) from bottom to top; each element is pushed and popped once, giving O(n) for next greater element, stock span and histogram problems.

Performance, complexity and limitations

• Every core stack/queue operation is O(1) time, O(1) auxiliary space; total space O(n).
• Advantages: trivially simple, predictable cost, excellent locality (array form), natural fit for order-dependent processing, no rebalancing.
• Limitations: no random access, no efficient search or sorted order, fixed capacity in the static form, and the access discipline itself - if the problem needs "the smallest" rather than "the newest" or "the oldest", a heap is the right structure, not a queue.
• Syllabus placement: AICTE model curriculum and UGC-CBCS B.Tech CSE place stacks and queues in the second-year Data Structures course, with a paired lab (array and linked implementations, expression conversion, circular queue). The GATE CS paper covers them under *Programming and Data Structures*; stack permutations and circular-queue index arithmetic are standard 1- and 2-mark items. There is no statutory code governing data structures - the standards that matter are language ones (ISO C, ISO C++ std::stack/std::queue/std::deque, Java Deque/ArrayDeque; Java's legacy Stack class is synchronised and discouraged in favour of ArrayDeque).

Key points

• Stack - LIFO; one access point called the top; push/pop/peek all O(1).
• Queue - FIFO; enqueue at rear, dequeue at front; all O(1).
• Underflow vs overflow - popping an empty structure vs pushing a full one; test before indexing.
• top = −1 - standard empty marker for an array stack; top == N−1 means full.
• False overflow - a linear array queue reports full while front slots lie empty; cured by a circular queue.
• Circular queue capacity - N−1 elements with the "one slot empty" convention, N with a count variable.
• Deque - insertion and deletion at both ends; generalises both stack and queue; input- and output-restricted variants exist.
• Amortised O(1) - a doubling dynamic-array stack copies at most 2n elements over n pushes.
• Call stack - each function call pushes an activation record; runaway recursion gives stack overflow.
• Postfix/prefix - need no parentheses or precedence; this is why compilers convert infix before evaluating.
• **^ is right-associative** - the one precedence exception that breaks naive conversion code.
• Postfix evaluation order - second_popped OP first_popped; getting this backwards ruins − and /.
• Stack permutations - the number of output orders obtainable from input 1..n is the Catalan number C(n); a permutation is impossible exactly when it contains a 3-1-2 pattern.
• Queue from two stacks - amortised O(1); stack from two queues - one operation must be O(n).
• Monotonic stack - O(n) total for next greater element, stock span, histogram area.
• BFS uses a queue, DFS uses a stack - the only structural difference between the two traversals.
• Priority queue is not a queue by arrival - it dequeues by key, and is built on a heap.
• Array vs linked - array is faster and smaller per element; linked is unbounded and never needs resizing.

Formulas and examples

Example 1 - Infix to postfix. Convert A + B * C − ( D / E + F ) * G.

Postfix = **A B C * + D E / F + G * −; the prefix form of the same expression is − + A * B C * + / D E F G**.

Example 2 - Postfix evaluation. Evaluate 5 6 2 + * 12 4 / −.

• Push 5, 6, 2 → stack [5, 6, 2].
• + → pop 2 and 6 → 6 + 2 = 8 → [5, 8].
• * → pop 8 and 5 → 5 × 8 = 40 → [40].
• Push 12, 4 → [40, 12, 4].
• / → pop 4 and 12 → 12 ÷ 4 = 3 → [40, 3].
• − → pop 3 and 40 → 40 − 3 = 37. Answer 37, matching 5×(6+2) − 12/4.

Example 3 - Circular queue. N = 10 slots (indices 0-9), front = 7, rear = 2, queue non-empty.

• Elements occupy 7, 8, 9, 0, 1, 2 → count = (2 − 7 + 10) % 10 + 1 = 5 + 1 = 6 elements.
• Enqueue: rear = (2 + 1) % 10 = 3; count becomes 7.
• Two dequeues: front = (7+1)%10 = 8, then 9; count becomes 5.
• With the "one slot empty" convention the queue would be full when rear reaches 5 - slot 6, the one just before front, is kept empty - i.e. at 9 elements, not 10.

Example 4 - Stack permutations. Input 1, 2, 3, 4 pushed in that order, pops interleaved freely.

• Number of distinct output sequences = C(4) = 8! / (4! × 5!) = 40,320 / (24 × 120) = 40,320 / 2,880 = 14.
• Is 3 4 1 2 achievable? Push 1,2,3 → pop 3 ✓ → push 4 → pop 4 ✓ → stack holds 1 (bottom), 2 (top), so the next pop must be 2, not 1. Not achievable. It contains the forbidden pattern (4, 1, 2) with 1 < 2 < 4 appearing as *large, small, middle*.
• 3 4 2 1 is achievable: push 1,2,3, pop 3, push 4, pop 4, pop 2, pop 1.

Example 5 - Deque: sliding-window maximum. Array [1, 3, −1, −3, 5, 3, 6, 7], window k = 3. Keep a deque of indices whose values decrease front→rear; drop indices that fall out of the window from the front, and pop smaller values from the rear before inserting.

• Windows and fronts: [1,3,−1] → 3; [3,−1,−3] → 3; [−1,−3,5] → 5; [−3,5,3] → 5; [5,3,6] → 6; [3,6,7] → 7.
• Output 3, 3, 5, 5, 6, 7 in O(n) - each index enters and leaves the deque once - against O(nk) for the naive scan.

Example 6 - Memory comparison. Storing 1,000,000 32-bit integers:

• Array stack: 4 bytes × 1,000,000 = 4 MB (plus up to 100% slack immediately after a doubling).
• Linked stack on a 64-bit machine: 4-byte value + 8-byte pointer padded to 16 bytes → 16 MB, four times the memory and far more cache misses.

# Monotonic stack: next greater element, O(n)
def next_greater(a):
    res, st = [-1] * len(a), []          # st holds indices, values decreasing
    for i, v in enumerate(a):
        while st and a[st[-1]] < v:
            res[st.pop()] = v
        st.append(i)
    return res
# next_greater([4, 5, 2, 25]) -> [5, 25, 25, -1]

/* Circular queue, count-variable convention: all N slots usable */
int q[N], front = 0, rear = -1, count = 0;
int enqueue(int x){ if(count==N) return 0;            /* overflow */
    rear=(rear+1)%N; q[rear]=x; count++; return 1; }
int dequeue(int *x){ if(count==0) return 0;           /* underflow */
    *x=q[front]; front=(front+1)%N; count--; return 1; }

Where it is used

• Compilers, interpreters and parsers: operator-precedence parsing, syntax checking of brackets, the activation-record stack of every running program - relevant to compiler and language-runtime roles at Oracle, SAP Labs, Adobe and Microsoft IDC.
• Operating systems and embedded firmware: ready queues for round-robin scheduling, interrupt stacks, ring buffers in UART/CAN drivers - core work at Bosch, Qualcomm India, Texas Instruments and Tata Elxsi, where a fixed-size circular queue is often the only buffer available on a microcontroller.
• Backend and payments systems: request queues and retry buffers in high-throughput Indian platforms - UPI switches, IRCTC booking, Zomato/Swiggy order pipelines - typically on Kafka or RabbitMQ, which are distributed queues preserving FIFO order within a single queue or partition.
• Web and application software: browser back/forward stacks, undo-redo in editors and design tools, call-stack traces in error monitoring, expression evaluators in spreadsheets and rule engines.
• Telecom and service operations: IVR and call-centre hold queues, token/queue-management systems in banks, passport Seva Kendras and hospitals - FIFO with a priority lane modelled as a second queue.
• Algorithms and analytics roles: BFS for shortest paths in unweighted road and social graphs, monotonic-stack techniques in stock-span and time-series analysis, deque-based sliding-window statistics in streaming pipelines.

Interview questions

• Q: What is the difference between a stack and a queue in one line? A: A stack removes the most recently inserted element (LIFO) using one end; a queue removes the earliest inserted element (FIFO) using opposite ends for insertion and deletion.
• Q: Why is a circular queue preferred over a linear array queue? A: A linear queue cannot reuse the slots freed at the front and declares false overflow; a circular queue wraps the indices with modulo N and reuses every slot.
• Q: In a circular queue, how do you distinguish full from empty if both give front == rear? A: Either keep one slot permanently empty (full when (rear+1)%N == front, capacity N−1) or maintain an explicit count or a flag, which keeps all N slots usable.
• Q: Implement a queue using two stacks - what is its complexity? A: Push onto an input stack; when dequeuing, if the output stack is empty, pour the entire input stack into it and pop. Each element moves at most twice, so it is amortised O(1) though a single dequeue can be O(n).
• Q: How do you get the minimum of a stack in O(1)? A: Maintain an auxiliary stack of running minima pushed alongside each element, or store the encoded value 2x − min when a new minimum arrives and recover the old minimum on pop.
• Q: How many output sequences can a stack produce from the input 1, 2, 3, 4, 5? A: The Catalan number C(5) = 10!/(5!·6!) = 42.
• Q: Given input 1,2,3,4,5 in order, can a stack output 4,5,3,1,2? A: No. Once 3 is popped, 1 and 2 remain with 2 above 1, so 2 must come out before 1; any output containing a *large, small, middle* (3-1-2) pattern is impossible.
• Q: Why do compilers convert infix to postfix? A: Postfix encodes precedence and associativity in the operand order, so evaluation needs a single left-to-right scan with one stack and no parentheses or lookahead.
• Q: What happens on a stack overflow in a recursive program? A: The call stack exhausts its reserved region (commonly 1-8 MB per thread) and the program dies with a segmentation fault in C/C++ or a JVM StackOverflowError; the cure is a correct base case, tail-recursion removal, or an explicit heap-allocated stack.
• Q: Which traversal uses a stack and which a queue, and why? A: DFS uses a stack because it must return to the most recent branching point; BFS uses a queue because it must finish all nodes at distance *d* before any at *d+1*, which also makes BFS give shortest paths in unweighted graphs.
• Q: Why is std::deque preferred to repeated vector::erase(begin()) for a queue? A: Erasing the front of a vector shifts all remaining elements, costing O(n) per dequeue; a deque gives O(1) at both ends.
• Q: Is a priority queue a queue? A: Only by name - it dequeues by key rather than by arrival order and is implemented on a heap, giving O(log n) insert and extract instead of O(1).

Common mistakes

• Checking overflow or underflow *after* incrementing or using the index, so the code writes outside the array or returns garbage from an empty stack.
• Using rear + 1 instead of (rear + 1) % N in a circular queue, or forgetting that the one-slot-empty convention holds only N−1 elements.
• Reversing the operands in postfix evaluation - computing first_popped OP second_popped - which silently gives the right answer for + and * but the wrong one for −, / and ^.
• Treating ^ as left-associative in infix-to-postfix conversion, so 2^3^2 is parsed as (2^3)^2 = 64 instead of 2^(3^2) = 512.
• Checking only the *count* of brackets instead of their *type and order*, so ([)] is wrongly reported as balanced.
• Forgetting to reset rear to NULL in a linked queue when the last node is dequeued, leaving a dangling pointer that corrupts the next enqueue.
• Claiming a stack can produce any permutation of its input, or that a doubling dynamic array is O(1) in the worst case rather than amortised.

Related topics

Arrays and strings · Linked lists · Heaps and priority queues · Graphs and their representation · Trees and binary search trees · Recursion and backtracking