CH 02

Stack

Data Structures · GATE

What is a stack?Stack kya hota hai?

A stack is a LIFO (last in, first out) list: elements are added and removed only at one end, called the top. Think of a pile of plates.Stack ek LIFO (last in, first out) list hai: elements sirf ek hi end se add aur remove hote hain, jise top kehte hain. Plates ke dher ki tarah socho — jo plate sabse upar rakhi, wahi sabse pehle uthegi.

OperationsOperations

Operation	Time	Notes
push(x)	O(1)	Overflow if the array is full
pop()	O(1)	Underflow if the stack is empty
peek() / top()	O(1)	Read without removing
isEmpty()	O(1)	top == −1 in the array version

#define MAX 100
int st[MAX], top = -1;

void push(int x) { if (top == MAX - 1) return; /* overflow */ st[++top] = x; }
int  pop(void)   { if (top == -1) return -1;   /* underflow */ return st[top--]; }

ApplicationsApplications

Function calls and recursion (call stack / activation records).
Expression conversion (infix → postfix/prefix) and evaluation.
Balanced-parentheses checking.
Undo/redo, browser back button, DFS.

Function calls aur recursion (call stack / activation records).
Expression conversion (infix → postfix/prefix) aur evaluation.
Balanced parentheses check karna.
Undo/redo, browser ka back button, DFS.

Infix to postfixInfix se postfix

Operand → write it to the output.
'(' → push.
')' → pop to output until '(' is popped (discard both brackets).
Operator → pop operators with higher precedence (or equal precedence if left-associative) to output, then push it.
End → pop everything left.
^ is right-associative, so an incoming ^ does not pop another ^.

Operand → seedha output mein likh do.
'(' → push karo.
')' → '(' milne tak sab pop karke output mein daalo (dono brackets discard).
Operator → jo operators higher precedence ke hain (ya equal, agar left-associative hai) unhe pop karke output mein daalo, phir isko push karo.
End → jo bacha hai sab pop kar do.
^ right-associative hai, isliye naya ^ purane ^ ko pop nahi karta.

Symbol	Stack	Output
a		a
+	+	a
b	+	a b
*	+ *	a b
c	+ *	a b c
end		a b c * +

Tipa + b * c → a b c * +. Precedence: ^ > * / > + −.a + b * c → a b c * +. Precedence: ^ > * / > + −.

Postfix evaluationPostfix evaluation

Scan left to right. Push operands. On an operator, pop the top two values — the first pop is the RIGHT operand, the second pop is the LEFT operand — apply the operator and push the result.Left se right scan karo. Operands ko push karo. Operator aaye toh top ke do values pop karo — pehla pop RIGHT operand hai, doosra pop LEFT operand — operator lagao aur result push kar do.

TipEvaluate 6 2 / 3 −: push 6, push 2, '/' → 6 / 2 = 3, push 3, '−' → 3 − 3 = 0.6 2 / 3 − evaluate karo: push 6, push 2, '/' → 6 / 2 = 3, push 3, '−' → 3 − 3 = 0.

Common mistakeCommon galtiGetting operand order wrong for − and / changes the answer. Second popped value OP first popped value.− aur / mein operand order galat hua toh answer badal jaata hai. Doosra popped value OP pehla popped value.

Counting stack permutationsStack permutations ginna

If 1, 2, …, n are pushed in order and pops can happen at any time, the number of possible output sequences is the nth Catalan number.Agar 1, 2, …, n order mein push hote hain aur pop kabhi bhi ho sakta hai, toh possible output sequences ki ginti nth Catalan number hoti hai.

Cₙ = C(2n, n) / (n + 1)      →  1, 1, 2, 5, 14, 42, …

TipFor n = 3 there are 5 valid sequences; 3 1 2 is impossible (after popping 3, 2 is on top of 1).n = 3 ke liye 5 valid sequences hain; 3 1 2 impossible hai (3 pop karne ke baad 2, 1 ke upar hota hai).

Quick revision

LIFO: push and pop happen at the top, both O(1).
Used for recursion, function calls, expression evaluation, undo and DFS.
Infix → postfix: operands go straight to output; pop operators of higher (or equal, if left-associative) precedence before pushing.
Postfix evaluation: push operands; on an operator, pop two (second pop is the left operand), push the result.
Number of valid push/pop sequences (permutations) of n elements = Catalan number C(2n, n) / (n + 1).

Done with this chapter? Now put it to use.Today's GATE question →