Home / Computer Science / Class XII / Stack
Stack — CUET Computer Science hero
Class XII 💻 Computer Science Ch 3 of 20

Stack

CUET unit: Stack

📌 Snapshot

  • Master the stack: last in first out, push and pop traces, postfix conversion and evaluation, step by step.
  • Overflow and underflow, and how a Python list becomes a stack with just append and pop.
  • Infix, prefix and postfix notation compared in one table, with the reason postfix never needs brackets.
  • Full trace tables for converting infix to postfix and evaluating postfix, the sums CUET repeats most.

📖 Detailed Notes

Written and reviewed by Rohit Singh, Computer Science & Commerce faculty at UniDrill (MCA, Osmania University · 6 years teaching). Based on NCERT Computer Science Class XII, Chapter 3.

How does the Back button know where to go?

Open five web pages one after another, then press Back five times. You visit them in exactly the reverse order. The browser does not need a clever search. It simply keeps the pages in a pile, adds each new page on top, and when you press Back it takes the top page away. That pile is a stack, and the rule it follows, last in first out, powers undo buttons, bracket checking in compilers and the way your calculator evaluates expressions.

What is a stack?

A data structure is a way of storing and organising data together with the operations that can be done on it efficiently. Strings, lists, tuples and sets are data types you already know. Stack and Queue are two classic structures built for a particular job.

A stack is a linear data structure, meaning its elements sit in a sequence. Elements are added and removed from the same end only, called the TOP. This gives the LIFO (Last In First Out) rule: the element inserted last is the first one removed. Think of a pile of plates, a stack of books, clothes piled in an almirah, or bangles on a wrist. You can only touch the one on top.

Application What goes on the stack Why last in first out fits
Reversing a string Each character, in order Characters come out in reverse
Undo in an editor Each change made The latest change is the first to undo
Browser Back button Each page visited You return to the most recent page first
Matching brackets Each opening bracket The most recent opening bracket must close first

PUSH and POP

Two operations define a stack. PUSH inserts an element at the TOP. POP removes the topmost element. Two error conditions go with them. Pushing onto a full stack causes an overflow. Popping from an empty stack causes an underflow.

Operation Does what Error if it cannot be done
PUSH Adds an element at the TOP Overflow (stack is full)
POP Removes and returns the TOP element Underflow (stack is empty)
Peek or top Reads the TOP element without removing it Underflow if empty
isEmpty Checks whether the stack has no elements None
size Counts the elements None

Worked example: tracing PUSH and POP. Start with an empty stack of glasses and follow these operations. The stack is written from bottom to top, so the right most item is the TOP.

Step Operation Value returned Stack after the step TOP
1 PUSH 1 none [1] 1
2 PUSH 2 none [1, 2] 2
3 POP 2 [1] 1
4 PUSH 3 none [1, 3] 3
5 PUSH 4 none [1, 3, 4] 4
6 POP 4 [1, 3] 3
7 POP 3 [1] 1
8 POP 1 [] none
9 POP underflow [] none

Notice that the values leave in an order that is not the order they arrived (2, then 4, 3, 1). The element 2 was pushed second but left first, because only the top is ever reachable. The common wrong step is to remove "the oldest" element, which is what a queue does.

Pause and predict: after PUSH 5, PUSH 7, POP, PUSH 9, POP, which element is on top?

Check your answer: 5. The stack goes [5], [5, 7], [5] (7 removed), [5, 9], [5] (9 removed). The last POP removes 9, because 9 was on top, and 5 is exposed again.

A stack in Python: a list with two methods

A Python list already behaves like a stack if you only work at its right end. append() adds an element at the end, which is PUSH. pop() removes and returns the last element, which is POP. So no separate TOP variable is needed: the last element is the TOP.

A Python list can grow as long as memory is available, so a list based stack practically never faces overflow. Underflow is still possible, so the pop function must check for an empty stack first.

Code
def isEmpty(glassStack):
    return len(glassStack) == 0
def opPush(glassStack, element):
    glassStack.append(element)
def size(glassStack):
    return len(glassStack)
def top(glassStack):
    if isEmpty(glassStack):
        print("Stack is empty")
    else:
        return glassStack[len(glassStack) - 1]
def opPop(glassStack):
    if isEmpty(glassStack):
        print("underflow")
    else:
        return glassStack.pop()
def display(glassStack):
    x = len(glassStack)
    for i in range(x - 1, -1, -1):
        print(glassStack[i])

The function top() reads the last element without removing it. display() prints from the top downwards, which is why its loop counts backwards from x - 1 to 0.

Code
glassStack = list()
opPush(glassStack, "G1")
opPush(glassStack, "G2")
opPush(glassStack, "G3")
print(top(glassStack))
print(opPop(glassStack))
print(size(glassStack))
display(glassStack)
opPop(glassStack)
opPop(glassStack)
opPop(glassStack)
Output
G3
G3
2
G2
G1
underflow

Read the output line by line. top() shows G3 without removing it. opPop() then removes and returns G3. The size is now 2. display() prints from the top, G2 then G1. The three pops at the end remove G2 and G1, and the third finds an empty stack and prints underflow.

Why pop() and not pop(0). pop() with no argument removes the last element, which is the TOP. pop(0) would remove the first element, the bottom of the stack, and that breaks the LIFO rule.

Beyond the textbook. For the exam: popping an empty stack is called underflow, and the helper function prints underflow. In reality: if you call pop() directly on an empty Python list, the language raises an IndexError with the message pop from empty list. "Underflow" is the name of the concept, and IndexError is how Python reports it when you skip the check.

Beyond the textbook. For the exam: a list based stack never overflows in practice. In reality: real programs do run out of stack. Every function call is pushed onto a stack inside the interpreter, and a function that keeps calling itself forever fills it. Python then stops with a RecursionError. That is a genuine stack overflow.

Applications in Python

Reversing a string. Push every character, then pop them all. The last character pushed is the first popped.

Code
def reverse(text):
    stk = list()
    for ch in text:
        stk.append(ch)
    result = ""
    while len(stk) > 0:
        result = result + stk.pop()
    return result
print(reverse("CUET"))
Output
TEUC

For "CUET" the stack grows [C], [C, U], [C, U, E], [C, U, E, T]. The pops then return T, E, U, C in that order.

Matching brackets. Push each opening bracket. On a closing bracket, pop one. The brackets balance only if nothing goes wrong and the stack is empty at the end.

Code
def balanced(expr):
    stk = []
    for ch in expr:
        if ch == "(":
            stk.append(ch)
        elif ch == ")":
            if len(stk) == 0:
                return False
            stk.pop()
    return len(stk) == 0
Expression What happens Stack at the end Result
(a+(b*c)) Push, push, pop, pop Empty True
((a+b) Push, push, pop One ( left over False
a+b)( The first ) finds an empty stack, so underflow is caught Not reached False

There are two ways to fail: a closing bracket with nothing to match (underflow), or an opening bracket left unclosed (non empty stack at the end).

Three ways to write an arithmetic expression

The usual way of writing x + y puts the operator between its operands. This is infix notation. Two other forms put the operator elsewhere. In prefix notation, also called Polish notation, the operator comes before its operands: +xy. It was introduced by the Polish mathematician Jan Lukasiewicz in the 1920s. In postfix notation, also called Reverse Polish, the operator comes after: xy+.

Infix Prefix Postfix
x + y +xy xy+
x * y + z +*xyz xy*z+
a + b * c +a*bc abc*+
(a + b) * c *+abc ab+c*
(x + y) / (z * 5) /+xy*z5 xy+z5*/

Why postfix and prefix exist. In infix, the expression a + b * c means a + (b * c) only because of the precedence rule (multiplication before addition), and (a + b) * c needs brackets to change that. In postfix the order of the operators alone decides what happens first: abc*+ and ab+c* are different strings with different meanings, and no brackets are ever needed. Postfix and prefix can therefore be evaluated in one scan from left to right, which is what makes them easy for a computer.

Converting infix to postfix

The algorithm uses a stack for operators and a string postExp for the answer. The rules for each symbol read from left to right are:

Symbol Action
Operand (variable or number) Add it straight to postExp
Left parenthesis ( Push it
Right parenthesis ) Pop operators into postExp until a left parenthesis appears, then discard both brackets
Operator Pop operators from the stack into postExp while the top has higher or equal precedence, stopping at a (. Then push the new operator
End of expression Pop everything left into postExp

Multiplication and division have higher precedence than addition and subtraction. Only operators and left brackets ever go on the stack, because operands go straight to the output.

Worked example: converting with brackets. Convert (x+y)/(z*8).

Symbol read Action Stack (bottom to top) postExp
( Left parenthesis: push ( empty
x Operand: add to postExp ( x
+ Operator: push ( + x
y Operand: add to postExp ( + xy
) Right parenthesis: pop + to postExp, discard both brackets empty xy+
/ Operator: push / xy+
( Left parenthesis: push / ( xy+
z Operand: add to postExp / ( xy+z
* Operator: push / ( * xy+z
8 Operand: add to postExp / ( * xy+z8
) Right parenthesis: pop * to postExp, discard both brackets / xy+z8*
End Pop all remaining: / empty xy+z8*/

The result is xy+z8*/. Notice that the second ( was pushed on top of /, and the * was pushed on top of the ( without popping anything: the left bracket acts as a wall that protects the operators below it.

Worked example: converting with precedence. Convert a+b*c-d.

Symbol read Action Stack (bottom to top) postExp
a Operand: add to postExp empty a
+ Operator: push + a
b Operand: add to postExp + ab
* Operator: push + * ab
c Operand: add to postExp + * abc
- Operator: pop * + first, then push - abc*+
d Operand: add to postExp - abc*+d
End Pop all remaining: - empty abc*+d-

The result is abc*+d-. When - arrives, the stack holds + and *. Both have precedence higher than or equal to -, so both are popped before - is pushed. When * arrived earlier, the top was +, which has lower precedence, so * was simply pushed on top.

The common wrong step is to forget "or equal". For a-b-c, equal precedence must pop the first -, giving ab-c-. If it did not, the result abc-- would compute a-(b-c), a different value.

Pause and predict: what is the postfix form of (a+b)*c?

Check your answer: ab+c*. The brackets force a+b to finish first, so + is popped when ) is read. Then c is added, and * is popped at the end.

Evaluating a postfix expression

Here the stack holds numbers. Read the expression left to right. An operand is pushed. For an operator, pop two operands, apply the operator, and push the result back. At the end, if the stack has exactly one element, that element is the answer. If it has more, the expression was not a valid postfix expression.

One detail causes most mistakes: the first element popped is the right operand, and the second popped is the left one. This matters for - and /.

Worked example: a first evaluation. Evaluate 7 8 2 * 4 / +.

Symbol read Action Stack (bottom to top)
7 Operand: push [7]
8 Operand: push [7, 8]
2 Operand: push [7, 8, 2]
* Pop 2 (right) and 8 (left), compute 8 × 2 = 16, push 16 [7, 16]
4 Operand: push [7, 16, 4]
/ Pop 4 (right) and 16 (left), compute 16 ÷ 4 = 4, push 4 [7, 4]
+ Pop 4 (right) and 7 (left), compute 7 + 4 = 11, push 11 [11]

The answer is 11. (In Python, 16 / 4 gives 4.0, so a program would show 11.0.)

Worked example: a longer evaluation. Evaluate 5 1 2 + 4 * + 3 -.

Symbol read Action Stack (bottom to top)
5 Operand: push [5]
1 Operand: push [5, 1]
2 Operand: push [5, 1, 2]
+ Pop 2 (right) and 1 (left), compute 1 + 2 = 3, push 3 [5, 3]
4 Operand: push [5, 3, 4]
* Pop 4 (right) and 3 (left), compute 3 × 4 = 12, push 12 [5, 12]
+ Pop 12 (right) and 5 (left), compute 5 + 12 = 17, push 17 [17]
3 Operand: push [17, 3]
- Pop 3 (right) and 17 (left), compute 17 - 3 = 14, push 14 [14]

The answer is 14. The wrong step is to subtract the other way round: reading 3 - as 3 - 17 would give -14. The right operand is the one popped first, which is 3, so the sum is 17 - 3.

Worked example: an invalid expression. For 4 5 + 6, the stack goes [4], [4, 5], [9] after +, then [9, 6]. Two elements remain, so the expression is invalid: it was missing an operator.

Task What is pushed on the stack
Infix to postfix conversion Operators and left brackets only
Postfix evaluation Operands and intermediate results only

Exam traps

Trap Why it tempts Truth
PUSH on a full stack is underflow Both words sound like "too little" Full stack gives overflow. Empty stack gives underflow
pop(0) implements POP Index 0 feels like the "first" thing pop() removes the last element, the TOP
Operands are pushed during conversion Operands are the "data" Conversion pushes operators. Operands go straight to the output
The first popped is the left operand Left comes first in writing The first popped is the right operand
Postfix is the prefix string reversed The names are "Polish" and "Reverse Polish" For x - y the prefix is -xy and the reverse is yx-, but the postfix is xy-
Postfix needs brackets Infix does Position alone fixes the order, so brackets are never used
A Python list stack can overflow Fixed stacks can A list grows until memory runs out, so overflow practically never happens
The TOP is the oldest element Oldest feels like the "first" The TOP is the most recently pushed element

60-second revision

Idea Remember
Stack Linear, one open end (TOP), LIFO
PUSH, POP Insert and delete at the TOP
Overflow, underflow Push on full, pop on empty
Python stack append() is PUSH, pop() is POP, last element is TOP
Helper functions isEmpty, size, top (peek), opPush, opPop, display
Infix, prefix, postfix Operator between, before, after the operands
Who Jan Lukasiewicz, 1920s, Polish (prefix) notation
Infix to postfix Operands to output, operators on the stack, pop for equal or higher precedence
Postfix evaluation Push operands, pop two at each operator, one element left is the answer
Operand order First popped is the right operand

Where this chapter connects

The other classic linear structure is Queue, which follows first in first out. Comparing the two is a favourite exam question. A stack of function calls is also how Python searches for a handler in Exception Handling in Python.

🎯 Practice MCQs

First 3 questions free · create a free account to unlock the rest — answers & explanations included, no payment needed

Q1. Which statement describes the LIFO principle of a stack?

▸ Show answer & explanation

Answer: C

LIFO means the most recently inserted element is the first to be removed. Option A describes a queue, option B describes a deque, and option D has the wrong end because a stack works at the top.

Q2. In Python, a stack is implemented using a list. Which pair of list methods performs PUSH and POP?

▸ Show answer & explanation

Answer: B

append() adds at the end of the list (PUSH) and pop() removes the last element (POP). Python lists have no add(), delete(), push() or pull() methods.

Q3. Statement I: Pushing an element onto a full stack causes underflow. Statement II: Popping an element from an empty stack causes overflow. Which option is correct?

▸ Show answer & explanation

Answer: D

Both statements have the names swapped. A push onto a full stack causes overflow, and a pop from an empty stack causes underflow.

🔒 12 more practice MCQs

Create a free account to unlock every MCQ in this chapter — answers and explanations included. No payment needed.

Already registered? Just log in and they'll all appear here.

📊 Previous-Year Questions

Practise with real CUET Computer Science previous-year papers — every question solved, with the correct answer and a step-by-step explanation.

View solved CUET PYQ papers →

Ready to drill Computer Science?

Unlock all MCQs, chapter tests, mocks & PYQs for ₹199/year.

Get UniDrill Pro