Back to CS Curriculum

Data Structures

CBSE Class 12 - Computer Science

Data Structures in Python

Data structures are fundamental concepts in computer science that help organize and store data efficiently. This chapter covers Stack, one of the most important linear data structures used in programming.

What is a Stack?

A Stack is a linear data structure where elements are added and removed only from one end, referred to as the "top." The Stack operates based on the Last In, First Out (LIFO) principle, meaning the most recently added element is the first to be removed.

Key Characteristics:

  • • Linear Data Structure: Stack is a linear data structure.
  • • LIFO Principle: Stack operates on the Last In, First Out (LIFO) principle.
  • • Operations at Top: Both insertion (PUSH) and deletion (POP) operations are carried out at the top of the stack.
  • • TOP Position: Initially, the top is considered to be empty or at a starting position. When inserting a value into the stack, the top position is updated, and the value is added. When removing a value, the top is adjusted accordingly.

Stack Terminology

Terms / OperationsDefinition / Explanation
TOPThe top represents the highest or last element added to the stack.
PUSHThe operation of adding a new element to the top of the stack is called a PUSH operation.
POPThe operation of removing or deleting the top element from the stack is known as the POP operation.
PEEKPEEK refers to viewing or inspecting the top element of the stack without removing it.
UNDERFLOWUNDERFLOW occurs when an attempt is made to remove an element from an empty stack, indicating that no elements are available to pop.
OVERFLOWOVERFLOW occurs when an attempt is made to add a new element to a full stack, indicating no space is left for insertion.

Stack Implementation in Python

The following code demonstrates a complete implementation of a Stack using Python list, including all basic operations:

Code Explanation:

  • • stack = []: Initializes an empty list to represent the stack.
  • • top = -1: Initializes the top pointer to -1, indicating an empty stack.
  • • push(value): Adds a new element to the top of the stack and increments the top pointer.
  • • pop(): Removes and returns the top element from the stack, handling UNDERFLOW condition.
  • • peek(): Views the top element without removing it.
  • • display(): Displays all stack elements from top to bottom.

Stack Operations Example

Let's trace through a series of stack operations to understand how the stack works:

Operation Sequence:

1. push(10) → Stack: [10], Top: 0
2. push(20) → Stack: [10, 20], Top: 1
3. push(30) → Stack: [10, 20, 30], Top: 2
4. pop() → Returns 30, Stack: [10, 20], Top: 1
5. peek() → Returns 20 (top element)
6. pop() → Returns 20, Stack: [10], Top: 0
7. pop() → Returns 10, Stack: [], Top: -1
8. pop() → UNDERFLOW (Stack is empty)

💡 Important Note: Always check for UNDERFLOW before performing a POP operation and for OVERFLOW before performing a PUSH operation (if the stack has a maximum size limit).

Applications of Stack

Stacks are used in various real-world applications:

1. Expression Evaluation

Used to evaluate arithmetic expressions (infix, postfix, prefix notation).

2. Function Call Management

Programming languages use stacks to manage function calls and local variables.

3. Undo/Redo Operations

Text editors and applications use stacks to implement undo/redo functionality.

4. Backtracking Algorithms

Used in algorithms like depth-first search (DFS) and solving puzzles.

Get in Touch