Stack - Class 12 Computer Science - Chapter 3 - Notes, NCERT Solutions & Extra Questions
Renews every month. Cancel anytime
Your personal doubt-solving assistant
Chatterbot AI gives you 100% accurate answers to your questions in an instant.
NCERT Solutions - Stack | NCERT | Computer Science | Class 12
💡 Have more questions?
Ask Chatterbot AINotes - Stack | Class 12 NCERT | Computer Science
Comprehensive Class 12 Notes on Stacks in Computer Science
Introduction to Stack
Definition and Concept
In Computer Science, a stack is a fundamental data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Stacks are essential for various algorithmic processes and have a broad range of applications in both programming and real life.
Real-Life Examples of Stacks
Real-life examples of stacks include:
- A stack of plates in a kitchen where you add or remove plates from the top.
- A pile of clothes where you take the cloth on the top first.
- Bangles worn on a wrist where you add or remove bangles from the end.
Here's an illustration:
Fundamental Operations on Stack
Overview of Push and Pop Operations
Two primary operations on a stack are:
- Push: Adds a new element on top of the stack.
- Pop: Removes the topmost element from the stack.
Think of a stack of glasses where you add or remove glasses from the top:
- Push Operation:
- Pop Operation:
Detailed Explanation on Push Operation
The push operation involves adding a new element to the stack. If the stack is full, attempting to add another element will cause a 'stack overflow'.
Example in Python:
def opPush(glassStack, element):
glassStack.append(element)
Detailed Explanation on Pop Operation
The pop operation involves removing the topmost element from the stack. Removing an element from an empty stack results in 'stack underflow'.
Example in Python:
def opPop(glassStack):
if len(glassStack) == 0:
print('underflow')
return None
else:
return glassStack.pop()
Implementing Stack in Python
Using List to Create a Stack
In Python, a stack can be created using a list. Python’s list built-in methods append()
and pop()
can be used to push and pop elements respectively.
Here's how you can create a stack of glasses:
glassStack = list() # create empty stack
Additional Stack Operations
-
Checking if Stack is Empty
def isEmpty(glassStack): return len(glassStack) == 0
-
Finding the Size of the Stack
def size(glassStack): return len(glassStack)
-
Displaying Stack Elements
def display(glassStack): print("Current elements in the stack are:") for element in reversed(glassStack): print(element)
Notations for Arithmetic Expressions
Different Types of Expressions
Arithmetic expressions can be represented in three different notations:
-
Infix: Operators are between the operands (e.g.,
x + y
). -
Prefix: Operators are before the operands (e.g.,
+ xy
). -
Postfix: Operators are after the operands (e.g.,
xy +
).
Here’s a visual representation:
graph LR
A(Infix) -->|Example| B(x*y + z)
C(Prefix) -->|Example| D(+ * x y z)
E(Postfix) -->|Example| F(x y * z +)
Conversion from Infix to Postfix
Here are the steps to convert an infix expression to postfix:
- Create an empty string for the postfix expression.
- Iterate through the infix expression character by character.
- Use a stack to temporarily hold operators and parentheses.
- Add operands directly to the postfix expression string.
- At the end, pop all remaining operators from the stack.
Example algorithm:
def infix_to_postfix(infix_expr):
stack = []
post_exp = ""
for char in infix_expr:
if char.isalnum(): # If operand, add to postfix expression
post_exp += char
elif char == '(': # If '(', push on stack
stack.append(char)
elif char == ')': # If ')', pop till '('
while stack and stack[-1] != '(':
post_exp += stack.pop()
stack.pop()
else: # If operator, handle precedence
while stack and precedence(char) <= precedence(stack[-1]):
post_exp += stack.pop()
stack.append(char)
while stack:
post_exp += stack.pop()
return post_exp
Evaluation of Postfix Expressions
Postfix expressions are evaluated using a stack:
- Traverse the expression from left to right.
- Push operands onto the stack.
- On encountering an operator, pop the necessary number of operands, apply the operator, and push the result back onto the stack.
Example algorithm:
def eval_postfix(postfix_expr):
stack = []
for char in postfix_expr:
if char.isdigit():
stack.append(int(char))
else:
b = stack.pop()
a = stack.pop()
if char == '+':
stack.append(a + b)
elif char == '-':
stack.append(a - b)
elif char == '*':
stack.append(a * b)
elif char == '/':
stack.append(a / b)
return stack.pop()
Conclusion
Understanding stacks is crucial for both algorithmic thinking and practical programming. Key points to remember include:
- Stacks are LIFO data structures.
- Basic operations are push and pop.
- Stacks can be efficiently implemented in Python using lists.
- They play a vital role in expression evaluation and memory management.
Mastering stacks will enhance your ability to handle complex computational problems and optimise your programming skills.
🚀 Learn more about Notes with Chatterbot AI