STACK — Complete Expanded Notes
STACK — Complete Expanded Notes
1. Definition of Stack
A Stack is a linear data structure that allows data to be inserted and removed only from one
end, called the top of the stack.
It follows a specific rule called LIFO — Last In, First Out.
The element that is inserted last into the stack is the first one to be removed.
Example: Stack of plates — last plate added is the first one removed.
2. Analogy (Real-Life Examples)
- Stack of Books: You remove the topmost book first.
- Browser History: The last visited page is opened first when you press 'Back'.
- Undo Feature: The last change is undone first.
3. Characteristics of Stack
1. Linear Structure – Elements are arranged sequentially.
2. Restricted Access – Only the top element can be accessed or modified.
3. Follows LIFO Principle – Last In, First Out.
4. Dynamic or Static – Can be implemented using arrays or linked lists.
5. Top Pointer – Points to the topmost element.
6. Stack Overflow/Underflow – Errors caused by overuse or empty stack.
4. Basic Operations
- push(x): Adds element x on top of stack.
- pop(): Removes top element.
- peek()/top(): Returns top element without removing.
- isEmpty(): Checks if stack is empty.
- size(): Returns number of elements in stack.
5. Representation
Example sequence: push(10) → push(20) → push(30) → pop()
Stack before pop: [10, 20, 30]
Stack after pop: [10, 20]
6. Implementation Methods
A. Using Array – Static, fixed size.
B. Using Linked List – Dynamic, flexible size.
7. Example Programs
Example 1: Stack using List in Python
------------------------------------
stack = []
[Link](10)
[Link](20)
[Link](30)
[Link]()
print(stack)
Example 2: Stack using Class
----------------------------
class Stack:
def __init__(self):
[Link] = []
def push(self, item):
[Link](item)
def pop(self):
if not self.is_empty():
return [Link]()
def peek(self):
if not self.is_empty():
return [Link][-1]
def is_empty(self):
return len([Link]) == 0
def size(self):
return len([Link])
Example 3: Balanced Parentheses
-------------------------------
def is_balanced(expression):
stack = []
for ch in expression:
if ch in "([{":
[Link](ch)
elif ch in ")]}":
if not stack:
return False
top = [Link]()
if (ch == ')' and top != '(') or (ch == ']' and top != '[') or (ch == '}' and top != '{'):
return False
return not stack
8. Applications of Stack
1. Expression evaluation
2. Function calls / recursion
3. Undo/Redo feature
4. Browser navigation
5. Syntax parsing
6. Memory management
7. Backtracking algorithms
9. Advantages
- Simple and easy to implement.
- Fast insertion and deletion (O(1)).
- Useful in recursion and nested data structures.
10. Disadvantages
- Limited access (only top element).
- Overflow and underflow possible.
- Not suitable for random access.
11. Time Complexity
All major operations (push, pop, peek) take O(1) time.
12. Real-World Examples
- Text editor undo/redo
- Web browser history
- Function call management
- Maze solving (backtracking)
- Data parsing
13. Summary Table
Property | Description
---------|-------------
Type | Linear Data Structure
Principle | LIFO (Last In, First Out)
Operations | push(), pop(), peek()
Implementation | Array or Linked List
Applications | Expression evaluation, recursion, undo/redo