Stacks

This lesson covers the stack — a fundamental Abstract Data Type (ADT) that follows the Last-In, First-Out (LIFO) principle. Stacks are used extensively in computing, from managing function calls to evaluating expressions.

---

What is a Stack?

A stack is an ordered collection of elements where:

• Items are added (pushed) to the top of the stack.
• Items are removed (popped) from the top of the stack.
• The most recently added item is always the first to be removed — LIFO.

Think of a stack of plates: you always add to the top and remove from the top. You cannot access plates in the middle without removing the ones above.

TOP →  [ 30 ]
       [ 20 ]
       [ 10 ]
BOTTOM

---

Stack Operations

Operation	Description	Time Complexity
push(item)	Add an item to the top of the stack.	O(1)
pop()	Remove and return the item from the top.	O(1)
peek() / top()	View the item on top without removing it.	O(1)
isEmpty()	Check whether the stack is empty.	O(1)
isFull()	Check whether the stack is full (array-based only).	O(1)
size()	Return the number of items in the stack.	O(1)

---

Array-Based Stack Implementation

A stack can be implemented using an array with a top pointer that tracks the index of the top element.

Pseudocode

CONSTANT MAX_SIZE = 100
DECLARE stack: ARRAY[0..MAX_SIZE-1] OF INTEGER
DECLARE top: INTEGER = -1

PROCEDURE push(item: INTEGER)
    IF top = MAX_SIZE - 1 THEN
        OUTPUT "Stack overflow"
    ELSE
        top = top + 1
        stack[top] = item
    END IF
END PROCEDURE

FUNCTION pop() RETURNS INTEGER
    IF top = -1 THEN
        OUTPUT "Stack underflow"
        RETURN -1
    ELSE
        item = stack[top]
        top = top - 1
        RETURN item
    END IF
END FUNCTION

FUNCTION peek() RETURNS INTEGER
    IF top = -1 THEN
        OUTPUT "Stack is empty"
        RETURN -1
    ELSE
        RETURN stack[top]
    END IF
END FUNCTION

FUNCTION isEmpty() RETURNS BOOLEAN
    RETURN top = -1
END FUNCTION

Python Implementation

class Stack:
    def __init__(self, max_size: int = 100):
        self.__stack = [None] * max_size
        self.__top = -1
        self.__max_size = max_size

    def push(self, item):
        if self.__top == self.__max_size - 1:
            raise OverflowError("Stack overflow")
        self.__top += 1
        self.__stack[self.__top] = item

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack underflow")
        item = self.__stack[self.__top]
        self.__top -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.__stack[self.__top]

    def is_empty(self) -> bool:
        return self.__top == -1

    def is_full(self) -> bool:
        return self.__top == self.__max_size - 1

    def size(self) -> int:
        return self.__top + 1

Exam Tip: In the exam, you may be asked to trace through a series of push and pop operations. Draw the stack after each operation, showing the top pointer. Remember: push increments the pointer first, then stores the item; pop retrieves the item first, then decrements the pointer.

---

Stack Overflow and Underflow