Stacks

Definition

• A Stack is a linear ADT following LIFO (Last-In-First-Out) — like a stack of plates, only the top is accessible

Core Operations (all O(1))

• push(x) — add element to top
• pop() — remove and return top element
• peek()/top() — view top element without removing
• isEmpty() — check if stack has no elements

Implementations

• Array-based: fixed size, risk of "stack overflow" if full
• Linked-list-based: dynamic size, no overflow (until memory exhausted)

Key Applications (frequently tested)

• Function call management — the call stack (recursion depends entirely on this)
• Expression evaluation — converting/evaluating infix, postfix (Reverse Polish), prefix expressions
• Balanced parentheses/bracket matching in compilers
• Undo/Redo functionality in editors
• Backtracking algorithms (maze solving, DFS)

Exam Angle

A guaranteed question type: "Convert infix expression to postfix using a stack" or "Check balanced parentheses using a stack" — practice both algorithms by hand. Know that DFS (graph traversal) uses a stack (explicit or via recursion), while BFS uses a queue — a classic paired MCQ trap.

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Exam Practice: ADT Specification of Stack

2016, Paper I, Q6(a) (8 marks) — Write Abstract Data Types (ADT) of Stack and Queue. Include the specifications of Add, Delete, IsEmpty, IsFull functions along with their respective functions.

Model answer (Stack half):

ADT Stack (LIFO — Last In First Out):

• Objects: a finite ordered list of elements of the same type, with one end designated as the "top".
• Add — Push(item): inserts item at the top. Precondition: stack not full. Postcondition: item becomes new top.
• Delete — Pop(): removes and returns the top item. Precondition: stack not empty. Postcondition: element below becomes the new top.
• IsEmpty(): returns true if the stack has zero elements (top == -1), else false.
• IsFull(): returns true if the stack has reached its maximum capacity (top == MAXSIZE-1), else false.
• Peek()/Top(): returns the top element without removing it.

Exam angle: FPSC explicitly names "Implementation of Stacks and Queues using ADTs" as a syllabus topic — this is the direct hit for that line item. Always state the pre/postconditions for each function, not just what it does; examiners award marks specifically for precondition checks (stack not full/not empty) since that is what separates a correct ADT spec from a vague description.

📝 Exam Practice: Postfix Expression Evaluation

2026, Paper I, Q5(c) (8 marks) — Write an algorithm with an example showing how a stack can be used to evaluate a postfix expression.

Algorithm:

Function EvaluatePostfix(expression):
    create an empty stack S
    for each token in expression (left to right):
        if token is an operand (number):
            push(S, token)
        else if token is an operator (+, -, *, /):
            operand2 <- pop(S)
            operand1 <- pop(S)
            result <- apply operator to (operand1, operand2)
            push(S, result)
    return pop(S)   // final result remaining on the stack

Worked example — evaluate 5 3 4 * + (equivalent to infix 5 + 3*4):

Result: 17, matching 5 + (3*4) = 17.

Key reasoning points: postfix notation already encodes precedence and associativity through token order, so each operator only ever needs its two most-recently produced operands — exactly the LIFO behaviour a stack provides. No parentheses or precedence table needs separate evaluation.

📝 Exam Practice: Overflow vs Underflow (MCQ pair)

2024, Paper I, Q17 (1 mark) — When we attempt to add the eleventh element to a stack with a size of 10, we encounter a circumstance known as:

• A. Garbage collection
• B. Underflow
• C. Overflow ✓
• D. None of these

2025, Paper I, Q16 (1 mark) — The process of deleting an element from an empty stack is called:

• A. Overflow
• B. Deletion
• C. Underflow ✓
• D. None of these

MCQ Trap: these two are frequently swapped by candidates under time pressure. Fix it with the mnemonic: Overflow = Over capacity (push on a full stack); Underflow = Under zero (pop on an empty stack).

📝 Exam Practice: What a Stack Physically Is

2025, Paper II, Q1 (1 mark) — A stack is:

• A. An 8 bit register in microprocessor
• B. A 16 bit register in microprocessor
• C. A set of memory location in R/WM reserved for storing information temporarily during the execution of computer. ✓
• D. A 16-bit memory address stored in program counter

Exam angle: this variant comes from the Computer Organization side of the syllabus but tests the same underlying concept — a stack is a region of read/write memory (not a fixed CPU register) used to hold data such as return addresses and local variables during execution. Recognize the ADT-level "Stack" (LIFO abstract structure) and this hardware-level "stack" (a reserved RAM region, e.g. the call stack) as the same idea at two levels of abstraction.

---n## Infix to Prefix ConversionnConverting infix directly to prefix is less intuitive than infix→postfix, so the standard technique reuses the postfix algorithm via three steps:n1. Reverse the infix expression token by token, and swap every ( with ) (and vice versa).n2. Convert this reversed-and-swapped expression to postfix using the ordinary infix→postfix (Shunting-Yard) algorithm.n3. Reverse the resulting postfix expression — this is the prefix form.n### Exam AnglenThe step people forget is swapping parentheses before reversing (or equivalently, reverse the token list, then swap brackets) — reversing without swapping brackets breaks the grouping and produces an invalid expression. Always sanity-check the final prefix answer by evaluating it (scan right-to-left, push operands, and on an operator pop left operand first, then right operand, computing left OP right) and confirming it matches the original infix's numeric result.n## 📌 More Sample & Repeated FPSC Questionsn### 📝 Exam Practice: Infix → Prefix, Two Worked Examplesn2021, Paper I, Q5(c) (6 marks) — Convert the following infix notation to prefix: (i) (30+23)*(43-21)/(84+7) (ii) 2*(1+(4*(2+1)+3))n**(i)** Reverse + swap parens: (7+84)/(21-43)*(23+30) → convert to postfix: 7 84 + 21 43 - / 23 30 + * → reverse for prefix:n*** + 30 23 / - 43 21 + 84 7nVerification: evaluating this prefix expression gives (30+23) × [(43−21)/(84+7)] = 53 × (22/91) ≈ 12.81, matching the original infix's value 53×22/91 ≈ 12.81 (multiplication/division regrouping doesn't change the numeric result).n(ii)** Reverse + swap parens: ((3+(1+2)*4)+1)*2 → convert to postfix: 3 1 2 + 4 * + 1 + 2 * → reverse for prefix:n*** 2 + 1 + * 4 + 2 1 3nVerification: evaluating right-to-left gives 2×(1+(4×(2+1)+3)) = 2×(1+15) = 2×16 = 32, matching the original infix exactly.nKey reasoning points:** both parts use the exact same 3-step reverse→convert→reverse method described above — the only work is careful, patient token-by-token bookkeeping. Always verify your final prefix answer numerically against the original infix expression before treating it as final.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-I · Q6(a) · 8 marks (stack part)

Q. Write the Abstract Data Types (ADT) of Stack and Queue. Include the specifications of Add, Delete, IsEmpty and IsFull.

Ans. (The queue part is on the Queues page.)

ADT Stack (LIFO)
  Data: ordered items, with a top pointer; capacity MAX
  Operations:
    Create()      : make an empty stack
    Push(x)       : precondition: not full;  post: x is on top      (Add)
    Pop()         : precondition: not empty; post: top removed and returned (Delete)
    Peek()        : returns the top item without removing it
    IsEmpty()     : true if top = -1
    IsFull()      : true if top = MAX - 1

void push(int x) { if (top == MAX - 1) cout << "Overflow"; else s[++top] = x; }
int  pop()       { if (top == -1) { cout << "Underflow"; return -1; } return s[top--]; }
bool isEmpty()   { return top == -1; }
bool isFull()    { return top == MAX - 1; }

2021 · Paper-I · Q5(c) · 6 marks

Q. Convert the infix expressions to prefix: (i) (30+23)(43-21)/(84+7) (ii) 2(1+(4*(2+1)+3)).

Ans.

• (i) * and / have equal precedence and associate left to right, so the expression is ((30+23)*(43−21)) / (84+7).
  • (30+23) → + 30 23; (43−21) → - 43 21; their product → * + 30 23 - 43 21; (84+7) → + 84 7.
  • Prefix: / * + 30 23 - 43 21 + 84 7
• (ii) innermost first: (2+1) → + 2 1; 4*(…) → * 4 + 2 1; (…)+3 → + *4 + 2 1 3; 1+(…) → + 1 +* 4 + 2 1 3; 2*(…) →
  • Prefix: * 2 + 1 + * 4 + 2 1 3
• Method: reverse the infix expression, swap brackets, convert to postfix with a stack, then reverse the result.

2026 · Paper-I · Q5(c) · 8 marks

Q. Write an algorithm with an example showing how a stack can be used to evaluate a postfix expression.

Ans.

create an empty stack
for each token in the postfix expression, left to right:
    if token is an operand: push it
    else (operator):
        b = pop();  a = pop()
        push( a operator b )
the single value left on the stack is the result

• Example: 5 6 2 + * 12 4 / -

• Result: 37. The time is O(n) for n tokens. The first operand popped is the right operand.

MCQs

2024 P-I · Q17. When we attempt to add the eleventh element to a stack with a size of 10, we encounter a circumstance known as:

• (A) Garbage collection
• (B) Underflow
• (C) Overflow ✅
• (D) None of these
• Answer: (C) Overflow.
• Why: pushing onto a full stack is an overflow. Underflow is the opposite (popping from an empty stack), and garbage collection is automatic freeing of unused memory.

2025 P-I · Q16. The process of deleting an element from an empty stack is called:

• (A) Overflow
• (B) Deletion
• (C) Underflow ✅
• (D) None of these
• Answer: (C) Underflow.
• Why: popping from an empty stack is an underflow. Overflow is pushing onto a full stack, and "deletion" is just the normal operation.