Siksha Sarovar

Siksha Sarovar (sikshasarovar.com) is a free educational web application that helps students in India learn programming and prepare for academic and competitive exams. The platform offers structured coding courses (C, C++, Python, Java, HTML, CSS, PHP, Power BI, AI, Machine Learning, Data Science), complete university curriculum notes for BCA/MCA students with previous year question papers, Class 10 and Class 12 CBSE/HBSE school notes, and dedicated preparation material for SSC, UPSC, Banking, Railway and other government exams. Browsing the site is completely free and requires no account. Users may optionally sign in with Google solely to save their learning progress, quiz scores and personal preferences across devices.

Privacy Policy | Terms of Service | Contact Siksha Sarovar | About Siksha Sarovar

v4.0.9 · PWA
Siksha Sarovar logo
Siksha Sarovar
Your Learning Universe

Siksha Sarovar is a free e-learning platform for coding courses, BCA university notes and competitive exam preparation. Optional Google sign-in saves your learning progress across devices.

Initializing knowledge base…
Compiling modules 0%

Unit 1: Detailed Component - Stacks

Lesson 3 of 14 in the free Data Structure notes on Siksha Sarovar, written by Rohit Jangra.

Stacks: The LIFO Structure

Definition: A Stack is a linear data structure where insertion and deletion are permitted at only one end, called the Top. Principle: LIFO (Last In, First Out). The last plate placed on the stack is the first one removed.

Stack Operations & Complexity

OperationDescriptionCondition CheckTime Complexity
PushAdd element to the TopCheck Overflow (Is stack full?)O(1)
PopRemove element from the TopCheck Underflow (Is stack empty?)O(1)
Peek / TopView top element without removingCheck UnderflowO(1)
isEmptyCheck if stack has no elementsO(1)
isFullCheck if stack is at capacityO(1)
SizeReturn number of elementsO(1)

Stack vs Queue — Key Differences

FeatureStackQueue
PrincipleLIFO (Last In, First Out)FIFO (First In, First Out)
InsertPush (at Top only)Enqueue (at Rear only)
DeletePop (from Top only)Dequeue (from Front only)
PointersSingle pointer (Top)Two pointers (Front, Rear)
AnalogyStack of platesQueue at ticket counter
Use CasesUndo, recursion, expression evaluationScheduling, BFS, buffering

Real-World Applications of Stacks

ApplicationHow Stack Is Used
Function Call StackEach function call pushes a frame; return pops it
Undo/RedoEach action pushed; Ctrl+Z pops the last action
Browser Back ButtonEach visited page pushed; Back pops it
Expression EvaluationPostfix/Prefix evaluation using operand stack
Parenthesis MatchingPush opening brackets; pop on closing brackets
RecursionSystem stack stores return addresses and local variables
DFS (Graph)Uses stack to track visited nodes

Polish Notations (Applications of Stack)

Named after Polish mathematician Jan Łukasiewicz, these notations remove the need for parenthesis.

NotationOperator PositionExample for A + BMachine Friendly?
InfixBetween operandsA + BNo (needs precedence rules)
Prefix (Polish)Before operands+ A BYes
Postfix (Reverse Polish)After operandsA B +Yes (easiest to evaluate)

Operator Precedence (High → Low):

  1. ^ (Exponentiation) — Right-to-Left associative
  2. *, / (Multiplication, Division) — Left-to-Right
  3. +, - (Addition, Subtraction) — Left-to-Right

Worked Example: Infix to Postfix Conversion

Convert: A * (B + C) - D / E

StepSymbolActionStackOutput
1AOperand → OutputA
2*Push to stack*A
3(Push to stack* (A
4BOperand → Output* (A B
5+Push to stack* ( +A B
6COperand → Output* ( +A B C
7)Pop until (*A B C +
8-Pop * (higher), Push --A B C + *
9DOperand → Output-A B C + * D
10/Push to stack- /A B C + * D
11EOperand → Output- /A B C + * D E
12EndPop allA B C + * D E / -

Result: A B C + * D E / -

Worked Example: Postfix Evaluation

Evaluate: 5 6 2 + * 12 4 / -

StepSymbolActionStack
15Push5
26Push5, 6
32Push5, 6, 2
4+Pop 2,6 → 6+2=8, Push5, 8
5*Pop 8,5 → 5×8=40, Push40
612Push40, 12
74Push40, 12, 4
8/Pop 4,12 → 12/4=3, Push40, 3
9-Pop 3,40 → 40-3=37, Push37

Result: 37