Stacks

ACompressed recap

🧾

A stack is LIFO: push, pop, peek in O(1); an array version uses top (−1 empty, MAX − 1 full) and must report overflow and underflow. Applications: bracket matching, infix → postfix/prefix with an operator stack (^ right-associative, higher or equal-left pops), and postfix evaluation with a value stack (right operand popped first). With a fixed input order, a stack can produce exactly C(n) = (2n choose n)/(n + 1) output orders; x … y … z with y < z < x is impossible.

BMerged rule card

3.2.1 Stack ADT; push/pop/peek; array implementation; overflow and underflow

• Stack = LIFO: push, pop, peek, isEmpty, isFull — all O(1).
• Array version: top = −1 empty; st[++top] = x; return st[top--]; full when top == MAX − 1.
• Overflow: push when full; underflow: pop/peek when empty.
• Uses: call stack, undo, bracket matching, expression evaluation, backtracking.

3.2.2 Stack applications: parenthesis matching; infix → postfix/prefix conversion; postfix evaluation

• Brackets: push openers; closer must match the top; empty at the end.
• Postfix: operand → output; ( push; ) pop to (; operator pops higher (or equal, if left-assoc) then pushes; end pops all.
• Precedence ^ > * / % > + −; ^ right-associative.
• Prefix: reverse, swap brackets, convert, reverse — or place operators before their operands from inside out.
• Evaluate postfix: operand push; operator pops right then left, pushes result.

3.2.3 Valid stack permutations; Catalan numbers

• Stack permutation: fixed input order, choose when to push/pop.
• Test by simulation, or forbid x … y … z with y z x.
• Catalan C(n) = (2n)!/((n + 1)!·n!) = (2n choose n)/(n + 1).
• C(0…7) = 1, 1, 2, 5, 14, 42, 132, 429.
• Also counts balanced bracket strings and push/pop sequences.

CInterleaved GATE-style questions

Q1MCQ1 markPostfix

Postfix of a + b * c - d:

• (A) a b c * + d -
• (B) a b c + * d -
• (C) a b c d * + -
• (D) a b + c * d -

Q2NAT2 marksEvaluate

Evaluate 6 2 3 + - 3 8 2 / + *.

Numerical answer: ________

Q3MCQ1 markAssociativity

Postfix of a ^ b ^ c (^ right-associative):

• (A) a ^ b c ^
• (B) a b c ^ ^
• (C) a b ^ c ^
• (D) ^ ^ a b c

Q4NAT1 markCatalan

How many output orders can 7 distinct items produce through one stack (fixed input order)?

Numerical answer: ________

Q5MCQ2 marksValidity

Input a, b, c, d. Which output is possible?

• (A) c a b d
• (B) d a b c
• (C) c d b a
• (D) d b c a

Q6NAT2 marksOverflow

An array stack of size 5 is empty. Operations: push ×3, pop ×1, push ×4, pop ×2. How many items remain (failed pushes do nothing)?

Numerical answer: ________

Q7MSQ1 markBrackets

Which strings would a stack checker reject?

• (A) (a+b]
• (B) {(a)[b]}
• (C) )(
• (D) ((a)

Q8MCQ1 markStack

Which needs a stack most naturally?

• (A) reading an array from index 0 upwards
• (B) undoing the last edits of a document
• (C) serving customers in arrival order
• (D) printing jobs in the order sent

Q9MCQ2 marksOutput

What does this print?

int st[50], top = -1;
void push(int x) { st[++top] = x; }
int pop(void) { return st[top--]; }

int evalPostfix(const char *e)
{
    int a, b;
    for (; *e; e++) {
        if (*e >= '0' && *e <= '9') { push(*e - '0'); continue; }
        b = pop();                 /* right operand comes off first */
        a = pop();
        if (*e == '+') push(a + b);
        else if (*e == '-') push(a - b);
        else if (*e == '*') push(a * b);
        else if (*e == '/') push(a / b);
    }
    return pop();
}

int main(void)
{
    printf("%d %d\n", evalPostfix("534*+2-"), evalPostfix("623+-382/+*"));
    return 0;
}

• (A) 19 7
• (B) 15 7
• (C) 15 -7
• (D) 17 7

DAnswer Vault