Stack

A stack is a linear data structure in which you may insert and delete at one end only. That single open end is called the top. Everything below it is sealed in.

Because the item you put in last is the one sitting on top, it is also the item you can take out first. That is the whole definition: a stack is LIFO — Last In, First Out.

You already use stacks every day without calling them that:

• A pile of steel plates at a canteen counter. You lift the top plate, and a washed plate goes back on top.
• The Back button in a browser. It takes you to the page you visited most recently, not the first one you opened.
• Ctrl+Z in any editor. Undo reverses your latest action first, then the one before it.
• Answer sheets an invigilator collects. The last sheet handed in lies on top of the bundle.

Contrast this with the queue at a Metro ticket counter, where the first person to arrive is served first. That is a different structure, and it is not in your syllabus. Everything in this chapter is LIFO.

The vocabulary the board expects:

Worked example. Six operations on a stack of student names. Watch which name comes out first.

# A stack of answer sheets on an invigilator's desk
stack = []                 # an empty stack

stack.append("Aarav")      # push
stack.append("Diya")       # push
stack.append("Kabir")      # push
print("Stack now :", stack)
print("Top item  :", stack[-1])

print("Popped    :", stack.pop())
print("Popped    :", stack.pop())
print("Stack now :", stack)

stack.append("Ishaan")
print("Stack now :", stack)
print("Top item  :", stack[-1])

Real output:

Stack now : ['Aarav', 'Diya', 'Kabir']
Top item  : Kabir
Popped    : Kabir
Popped    : Diya
Stack now : ['Aarav']
Stack now : ['Aarav', 'Ishaan']
Top item  : Ishaan

Trace it operation by operation. In the table the list is written bottom to top, exactly as Python prints it:

The proof of LIFO is in the third line of the output. Kabir went in last and came out first. Aarav went in first and was still sitting at the bottom, untouched, at the end. Diya could not be reached until Kabir was removed — in a stack you cannot pull an item out from the middle.

Python has no built-in stack type. The syllabus tells you to build one on a list, and a list already gives you every operation you need.

The first decision is which end of the list is the top. The answer is the end — the highest index — and there is a hard reason for it, not just a convention.

append() and pop() at the end do not move any other element. insert(0, x) and pop(0) must shift every remaining element one position across. Here is that cost measured with the timeit module: 200000 push-plus-pop pairs on a list of 100000 items.

import timeit

t_end   = timeit.timeit("s.append(1); s.pop()",
                        setup="s=list(range(100000))", number=200000)
t_front = timeit.timeit("s.insert(0,1); s.pop(0)",
                        setup="s=list(range(100000))", number=200000)
print("append/pop at end   :", round(t_end, 4), "sec")
print("insert/pop at front :", round(t_front, 4), "sec")

Output from one run on an ordinary laptop:

append/pop at end   : 0.0198 sec
insert/pop at front : 21.1736 sec

Over a thousand times slower for exactly the same number of operations. Run it on your own machine and the two numbers will be different — timings depend on the computer and on whatever else it happens to be doing — but the size of the gap is the point, and the gap does not go away. So the rule is settled: the last element of the list is the top of the stack. This benchmark is background reading; the board never asks you to time anything.

That gives this mapping, which is worth memorising as a block:

Worked example — the standard function set. Write your stack once in this shape and it will answer almost every stack question in the paper. Note that display() walks backwards so that the top prints first, and that it removes nothing.

def isEmpty(stk):
    if stk == []:
        return True
    else:
        return False

def push(stk, item):
    stk.append(item)
    top = len(stk) - 1
    return top

def pop(stk):
    if isEmpty(stk):
        return "Underflow"
    else:
        return stk.pop()

def peek(stk):
    if isEmpty(stk):
        return "Underflow"
    else:
        top = len(stk) - 1
        return stk[top]

def display(stk):
    if isEmpty(stk):
        print("Stack is empty")
    else:
        top = len(stk) - 1
        print(stk[top], "<-- top")
        for i in range(top - 1, -1, -1):
            print(stk[i])

# ---- driver code ----
Stack = []
print("top index after push:", push(Stack, "Roll-1"))
print("top index after push:", push(Stack, "Roll-2"))
print("top index after push:", push(Stack, "Roll-3"))
display(Stack)
print("peek :", peek(Stack))
print("pop  :", pop(Stack))
display(Stack)
print("List behind the stack:", Stack)

Real output:

top index after push: 0
top index after push: 1
top index after push: 2
Roll-3 <-- top
Roll-2
Roll-1
peek : Roll-3
pop  : Roll-3
Roll-2 <-- top
Roll-1
List behind the stack: ['Roll-1', 'Roll-2']

Two things to notice. peek and pop both returned Roll-3, but only pop shortened the stack — that is the whole difference between them. And the last line prints the ordinary list underneath: a stack is not a new kind of object, it is a list you have agreed to use in a disciplined way.

Two traps that cost marks. First, pop() with no argument removes the last item, but pop(0) removes the first — that is not stack behaviour at all.

data = [10, 20, 30, 40]

print(data.pop())      # no argument -> removes the LAST item (stack behaviour)
print(data)

print(data.pop(0))     # argument 0 -> removes the FIRST item (NOT a stack)
print(data)

40
[10, 20, 30]
10
[20, 30]

Second, append() changes the list in place and returns None. Assigning its result destroys your stack, and the error only shows up much later:

t = []
t = t.append(9)
print("t after t = t.append(9) :", t)

t after t = t.append(9) : None

Underflow is the case the board actually tests, and it is the one your code must handle. It happens when you pop or peek a stack that has nothing left in it.

Here is what an unguarded stack does. The first pop succeeds and empties the stack; the second one crashes and the program dies on the spot.

stack = [5]
print(stack.pop())     # works, the stack is now empty
print(stack.pop())     # UNDERFLOW - this line crashes
print('never reached')

Real output — note that the fourth line never ran and the program ended with a non-zero exit code:

5
Traceback (most recent call last):
  File "", line 3, in 
    print(stack.pop())     # UNDERFLOW - this line crashes
          ~~~~~~~~~^^
IndexError: pop from empty list

Three things in that traceback are worth reading properly. Python echoes the whole of line 3, trailing comment and all, and draws ~~~~~~~~~^^ under the exact call that failed. The file is shown as only because this transcript was captured by feeding the lines straight to Python; run the same code from a saved .py file and that spot holds the path of your file instead. The last line is the one to memorise — the rest of the traceback changes with where and how you ran it.

Peeking an empty stack fails too, but with a different message. Examiners ask for the exact wording, so learn both:

stack = []
print(stack[-1])

Traceback (most recent call last):
  File "", line 2, in 
    print(stack[-1])
          ~~~~~^^^^
IndexError: list index out of range

Both are IndexError, but pop from empty list comes from the .pop() method and list index out of range comes from subscripting with [-1]. Writing stk[len(stk)-1] instead of stk[-1] changes nothing: on an empty stack that is stk[-1] too, and it raises the same list index out of range.

The fix is always the same: check for empty first. A correct implementation never lets the crash happen. It tests the stack and returns something sensible instead.

def pop(stk):
    if len(stk) == 0:                 # guard FIRST
        return None                   # sentinel: "nothing came back"
    return stk.pop()

def peek(stk):
    if len(stk) == 0:
        return None
    return stk[-1]

stack = [5]
print("peek :", peek(stack))
print("pop  :", pop(stack))
print("pop  :", pop(stack))           # underflow - handled, no crash
print("peek :", peek(stack))
print("Program finished normally")

Real output:

peek : 5
pop  : 5
pop  : None
peek : None
Program finished normally

The program now runs all the way to the end. Returning None is right for code that other code will call. In a board answer it is usually better to return or print the word Underflow or Stack Empty, because the question normally asks for a message. Either way, the guard comes before the operation, never after.

All three empty-tests mean the same thing. Use whichever reads best in your answer:

stack = []
print("Truth value of empty stack :", bool(stack))
stack.append(7)
print("Truth value of [7]         :", bool(stack))

# the three empty-checks that all mean the same thing
s = []
print(s == [], len(s) == 0, not s)

Truth value of empty stack : False
Truth value of [7]         : True
True True True

Because an empty list is falsy, while len(stk) > 0: and while stk: are interchangeable.

Overflow is the mirror case, and in Python it is largely theoretical. A list grows as long as memory allows, so a list-based stack does not fill up by itself. Overflow exists only if you impose a maximum size:

MAX = 3                      # capacity we choose to impose

def push(stk, item):
    if len(stk) == MAX:
        print("Overflow! Stack is full, cannot push", item)
    else:
        stk.append(item)
        print("Pushed", item, "->", stk)

s = []
push(s, "UPI-1")
push(s, "UPI-2")
push(s, "UPI-3")
push(s, "UPI-4")
print("Final stack:", s)

Pushed UPI-1 -> ['UPI-1']
Pushed UPI-2 -> ['UPI-1', 'UPI-2']
Pushed UPI-3 -> ['UPI-1', 'UPI-2', 'UPI-3']
Overflow! Stack is full, cannot push UPI-4
Final stack: ['UPI-1', 'UPI-2', 'UPI-3']

So the honest exam answer is: underflow can happen on any Python stack and must always be guarded; overflow happens only when the program sets a size limit (or the machine genuinely runs out of memory).

Stack questions in the CBSE paper are remarkably consistent. You are handed a list or a dictionary, you push only the entries that satisfy a condition, and then you pop everything and display it. Learn that shape and the marks come easily.

Worked example 1 — a dictionary of prices in rupees. Push the names of items costing more than 500, then pop them all.

# Prices in rupees at a school stationery counter
items = {"Pen": 20, "Geometry Box": 250, "Scientific Calculator": 1200,
         "School Bag": 899, "Notebook": 60, "Drawing Board": 540}

def push_costly(stk, d):
    for name in d:
        if d[name] > 500:
            stk.append(name)

def pop_all(stk):
    if len(stk) == 0:
        print("Stack empty - nothing to pop")
        return
    while len(stk) > 0:
        print("Popped:", stk.pop())
    print("Stack empty")

stack = []
push_costly(stack, items)
print("Stack after pushing :", stack)
pop_all(stack)

Real output:

Stack after pushing : ['Scientific Calculator', 'School Bag', 'Drawing Board']
Popped: Drawing Board
Popped: School Bag
Popped: Scientific Calculator
Stack empty

Two points worth marks. Looping for name in d gives you the keys, so d[name] is needed for the value. And because Python keeps a dictionary in insertion order, the stack fills in that order — Scientific Calculator went in first, so it comes out last. Also note that more than 500 is a strict test: an item priced exactly 500 would not be pushed.

Worked example 2 — a list of numbers, with the empty case handled. This is the version that separates full marks from partial marks, because it survives the case where nothing qualifies.

def PUSH(Arr):
    stack = []
    for num in Arr:
        if num % 5 == 0:
            stack.append(num)
    if len(stack) > 0:
        print("Stack:", stack)
    else:
        print("Empty Stack")
    return stack

def POP(stack):
    if len(stack) == 0:
        print("Underflow")
        return None
    return stack.pop()

s = PUSH([12, 25, 7, 40, 55, 9, 100])
print("Popped:", POP(s))
print("Popped:", POP(s))
print("Now   :", s)

t = PUSH([1, 2, 3, 4])
print("Popped:", POP(t))

Real output:

Stack: [25, 40, 55, 100]
Popped: 100
Popped: 55
Now   : [25, 40]
Empty Stack
Underflow
Popped: None

The last three lines are the ones that earn the mark. No number in [1, 2, 3, 4] is divisible by 5, so the stack stays empty, PUSH prints Empty Stack instead of an empty pair of brackets, and POP reports Underflow instead of crashing.

Worked example 3 — a stack of records. An item pushed onto a stack need not be a single number. It can be a whole list.

# A stack holding whole records (each record is a list)
stack = []

def push_book(stk, bno, title, price):
    stk.append([bno, title, price])

def pop_book(stk):
    if not stk:
        return "Underflow"
    return stk.pop()

push_book(stack, 101, "Sumita Arora CS", 545)
push_book(stack, 102, "NCERT CS Part 2", 180)
push_book(stack, 103, "Together With CS", 420)

print("Stack :", stack)
print("Top   :", stack[-1])
print("Pop   :", pop_book(stack))
print("Pop   :", pop_book(stack))
print("Pop   :", pop_book(stack))
print("Pop   :", pop_book(stack))

Real output:

Stack : [[101, 'Sumita Arora CS', 545], [102, 'NCERT CS Part 2', 180], [103, 'Together With CS', 420]]
Top   : [103, 'Together With CS', 420]
Pop   : [103, 'Together With CS', 420]
Pop   : [102, 'NCERT CS Part 2', 180]
Pop   : [101, 'Sumita Arora CS', 545]
Pop   : Underflow

append() put each three-element list in as one stack item, which is what you want. Had you written extend() the record would have been flattened into three separate items and the stack would be nonsense. The fourth pop hits the guard and returns Underflow rather than raising IndexError.

Two applications appear again and again, and both work only because the structure is LIFO. If you understand why, you can reconstruct the code in the exam hall without memorising it. Nothing here needs anything beyond push, pop and a list.

Application 1 — reversing a string. Push every character onto the stack, then pop them all back. The first character pushed is the last one popped, so the order flips for free. You do nothing to reverse it; the data structure does it.

def reverse_using_stack(text):
    stack = []
    for ch in text:          # PUSH every character
        stack.append(ch)
    result = ""
    while len(stack) > 0:    # POP them back - comes out reversed
        result = result + stack.pop()
    return result

print(reverse_using_stack("PRIODEMY"))
print(reverse_using_stack("MALAYALAM"))
print(reverse_using_stack("Delhi"))

word = "NAMAN"
if reverse_using_stack(word) == word:
    print(word, "is a palindrome")
else:
    print(word, "is not a palindrome")

Real output:

YMEDOIRP
MALAYALAM
ihleD
NAMAN is a palindrome

MALAYALAM comes back unchanged, which is precisely what palindrome means — so the same function gives you a two-line palindrome checker, as the last two lines show.

Application 2 — checking balanced parentheses. This is the classic. Push every opening bracket. When a closing bracket arrives, pop the stack and check that the two are partners. The stack is the right tool because brackets nest: the bracket you must close next is always the most recent one you opened, which is LIFO exactly.

There are three distinct ways an expression can fail:

1. A closing bracket arrives when the stack is empty — nothing was open to close.
2. The bracket popped is the wrong partner, as in {[(])}.
3. The string ends with items still on the stack — something was opened and never closed.

def is_balanced(expr):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in expr:
        if ch in "([{":
            stack.append(ch)                  # opening -> push
        elif ch in ")]}":
            if len(stack) == 0:               # closing with nothing open
                return False
            if stack.pop() != pairs[ch]:      # wrong partner
                return False
    return len(stack) == 0                    # leftovers means unclosed

tests = ["(a+b)*(c-d)", "[(a+b)*c]", "(a+b))", "((a+b)",
         "{[()]}", "{[(])}", "a+b", "((()))"]
for t in tests:
    print(t.ljust(12), "->", is_balanced(t))

Real output:

(a+b)*(c-d)  -> True
[(a+b)*c]    -> True
(a+b))       -> False
((a+b)       -> False
{[()]}       -> True
{[(])}       -> False
a+b          -> True
((()))       -> True

Read the three failures against the three cases. (a+b)) fails on case 1 — the second closing bracket meets an empty stack. ((a+b) fails on case 3 — one opener is still on the stack when the loop ends. {[(])} fails on case 2 — the ] pops a (, and ( is not the partner of ]. And a+b has no brackets at all and is correctly reported balanced: an empty stack at the end is a pass, not a failure.

The order of the two checks inside the elif matters. The empty test must come first. If it did not, an input like )( would make stack.pop() raise IndexError instead of returning False — the underflow guard from the previous section, doing real work.

Application 3 — the browser Back button. The same structure, in a product you use daily. Every page you open is pushed; Back is a pop.

# Browser "Back" button: every page you open is pushed
history = []

def visit(page):
    history.append(page)
    print("Opened :", page)

def back():
    if len(history) <= 1:
        print("Back   : no previous page")
        return None
    history.pop()                 # throw away the current page
    print("Back   :", history[-1])
    return history[-1]

visit("priodemy.com")
visit("priodemy.com/courses")
visit("priodemy.com/courses/python")
back()
back()
back()
print("History:", history)

Real output:

Opened : priodemy.com
Opened : priodemy.com/courses
Opened : priodemy.com/courses/python
Back   : priodemy.com/courses
Back   : priodemy.com
Back   : no previous page
History: ['priodemy.com']

The third back() is the underflow case wearing a different hat: only the first page is left, there is nothing behind it, so the function refuses instead of crashing. This is why every browser greys out the Back button on the first page of a tab.