Stack Data Structure: Operations, Applications and Worked Examples

A stack looks easy until a problem combines top updates, operand order, and empty or full conditions. One missed step changes the answer. Stacks use LIFO and support core operations, expression evaluation, recursion, and exam-style traces. Stack states are shown from bottom to top, so each state change is visible.

Stack data structure: LIFO, top, and the ADT

A stack is a linear abstract data type where insertion and deletion happen only at the top. It follows last in, first out, or LIFO. After push(12), push(7), and push(25), the next pop() must return 25, not 12, because 25 entered last.

The stack ADT is the behavioural contract. It provides push, pop, peek, isEmpty, and sometimes size. An array or a linked list is only the storage choice used to honour that contract.

The array stack uses a fixed capacity of 4 and zero-based indexing. An empty stack has top = -1; a full one has top = 3. push(x) checks for space, increments top, then stores x at A[top]. pop() checks for underflow, saves A[top], decrements top, and returns the saved value.

Core stack operations and one complete trace

Now trace the capacity-4 array, with each stack written bottom to top:

1. Start with [], top = -1.

2. push(12) gives [12], top = 0.

3. push(7) gives [12, 7], top = 1.

4. push(25) gives [12, 7, 25], top = 2.

5. peek() returns 25; the stack and top do not change.

6. pop() returns 25 and leaves [12, 7], top = 1.

7. push(9) gives [12, 7, 9], top = 2.

8. push(4) gives [12, 7, 9, 4], top = 3.

9. push(31) reports overflow. The stack remains [12, 7, 9, 4].

A linked-list stack keeps the same ADT but uses its head as the top. push(12), push(7), and push(25) create 25 -> 7 -> 12 -> null. A pop() returns 25 and leaves 7 -> 12 -> null. Head changes take constant time without a fixed capacity, but every node needs a link and an allocation.

Infix, postfix, and prefix expressions

Consider the expression (8 + 2) * (9 - 5) / 2. Its postfix form is 8 2 + 9 5 - * 2 /, while its prefix form is / * + 8 2 - 9 5 2. During conversion, precedence and parentheses decide when waiting operators are popped.

Evaluate the postfix form one token at a time:

The final value is 20. For a b -, the first popped value is the right operand and the second is the left. Reversing them would incorrectly turn 9 - 5 into 5 - 9.

Parentheses, recursion, and classic stack applications

For balanced-symbol checking, scan [{(a+b)*c}-d] from left to right. Push [, {, and (. Pop ( on ), { on }, and [ on ]. The stack ends empty, so the expression is valid. In [(a+b]*c), ] meets ( at the top, making the expression invalid immediately.

Recursion uses a runtime call stack. For factorial(4), calls create frames fact(4) -> fact(3) -> fact(2) -> fact(1). The base case returns 1. Unwinding then gives fact(2) = 2 * 1 = 2, fact(3) = 3 * 2 = 6, and fact(4) = 4 * 6 = 24. A call-stack frame holds return information and local state. Heap storage is a separate concept.

The same mechanism supports undo history, backtracking, and depth-first search. Browser navigation commonly uses one stack for back history and another for forward history. For the FIFO counterpart, the earlier Queue Data Structure: Operations, Circular Queues and Worked Examples for GATE traces circular indexing and two-stack queues. Stack problems instead concentrate on LIFO operand order, expression evaluation, and call-stack unwinding.

Complexity, implementation choices, and traps

Arrays offer good memory locality. Linked lists avoid fixed capacity but add per-node link and allocation overhead. Neither representation makes random access efficient under the stack contract.

Implementation errors break invariants. Incrementing top in the wrong order causes an off-by-one write. Popping before checking isEmpty() causes underflow. Accepting a fifth value in a capacity-4 array crosses the boundary. Removing a value without returning or saving it breaks later computation.

Reasoning errors are common too. peek() does not delete. In [12, 7, 9, 4], the top is 4, not 12. Subtraction and division need the correct operand order. Write every intermediate state.

How GATE and interviews test stacks

Try a short trace. The initial stack is [3, 6], with 6 on top. Apply push(4), pop(), push(9), push(1), and pop():

1. push(4) gives [3, 6, 4].

2. pop() returns 4 and leaves [3, 6].

3. push(9) gives [3, 6, 9].

4. push(1) gives [3, 6, 9, 1].

5. pop() returns 1 and leaves [3, 6, 9].

The popped values are 4 and 1, the final stack is [3, 6, 9], and the final top is 9. In an objective question, write these states before selecting an answer.

Common question shapes include operation traces, infix or postfix conversion, expression evaluation, recursion output, implementation choices, and application selection. The GATE question types guide explains MCQ, MSQ, and NAT response formats.

An interview extension is a minimum stack. After push(5), push(2), and push(8), the data stack is [5, 2, 8], while a second minima stack is [5, 2]. getMin() returns 2. Popping 8 leaves the minimum at 2; popping 2 returns the minimum to 5. The second stack keeps getMin() at O(1).

Stack in the short version and the next step

• A stack allows insertion and deletion at one end.

• LIFO means the latest value pushed is the first value popped.

• top marks the active boundary.

• Core operations are constant time when no resize occurs.

• Stacks handle delayed work, reversal, recursion, and backtracking.

• Check underflow and fixed-array overflow before changing state.

As a self-check, reproduce the capacity-4 trace and the postfix result 20 without looking back. For structured preparation, use GATE Guidance by Sanchit Sir. Use the GATE Test Series for timed practice, and browse the GATE category for the current course set.