Stack (Data Structure)

Where this sits in GATE

Stacks are listed in Programming and Data Structures, Section 4 of the GATE 2027 CS syllabus, alongside arrays, queues, linked lists, trees, binary heaps and graphs. In the tracker's GATE CS pack they sit under Programming and Data Structures.

What a stack is

A stack is a last-in, first-out (LIFO) collection: the last item added is the first removed. It supports three operations, each in constant time:

• push(x): put $x$ on top.
• pop(): remove and return the top item.
• peek(): read the top item without removing it.

In an array implementation of capacity $n$, a variable 'top' holds the index of the top item (−1 when empty). Pushing onto a full stack is an overflow; popping an empty one is an underflow.

Worked example: tracing operations

Starting from an empty stack, perform: push 4, push 7, pop, push 2, push 9, pop, pop, push 5.

1. push 4, push 7: the stack is [4, 7] (top on the right).
2. pop removes 7: [4].
3. push 2, push 9: [4, 2, 9].
4. pop removes 9, pop removes 2: [4].
5. push 5: [4, 5].

The values popped, in order, are 7, 9, 2, and the final stack is [4, 5].

Worked example: evaluating a postfix expression

Evaluate the postfix expression '5 3 2 × + 4 −'. Push each number; on an operator, pop two values, apply it (second popped on the left), and push the result.

1. Push 5, 3, 2: [5, 3, 2].
2. '×': pop 2 and 3, push $3 \times 2 = 6$: [5, 6].
3. '+': pop 6 and 5, push $5 + 6 = 11$: [11].
4. Push 4: [11, 4]. '−': pop 4 and 11, push $11 - 4 = 7$: [7].

The answer is 7, the single value left on the stack.

Worked example: infix to postfix

Convert $A + B * (C - D) / E$ to postfix. Operands go straight to the output; operators wait on a stack and leave when an operator of lower or equal precedence arrives, or at a closing bracket. The result is:

Reading it back: $C - D$ first, then multiply by $B$, divide by $E$, and finally add $A$.

Worked example: which pop orders are possible?

The numbers 1, 2, 3 are pushed in that order, with pops allowed at any time. Can the output be 3, 1, 2?

Solution: To pop 3 first, 1 and 2 must already be on the stack with 2 above 1. The next pop must then be 2, not 1, so 3, 1, 2 is impossible. Of the 6 orders, exactly 5 are possible: 123, 132, 213, 231 and 321.

Common mistakes

• Reversing operands in postfix evaluation. For '−' and '÷', the second value popped goes on the left: '8 2 ÷' is 4, not 0.25.
• Checking for underflow after popping. Check that the stack is non-empty before you pop.
• Treating ^ as left-associative. Exponentiation is right-associative, so $2^{3^2}$ is $2^9$, and the infix-to-postfix rule changes for it.
• Confusing a stack with a queue. A queue is first-in, first-out.

Where this comes up in exams

The GATE 2027 CS syllabus lists stacks under Section 4, Programming and Data Structures, together with programming in C, recursion, arrays, queues, linked lists, trees, binary search trees, binary heaps and graphs.

Checked against GATE 2027 CS syllabus. Syllabi can change from year to year, so confirm with the latest official notification for your exam.

• Fit it into your week with the free timetable generator.
• Mark it off as you revise in the syllabus tracker.
• See how long you have left: GATE 2027 countdown.