2nd PUC Computer Science Chapter 3 – Stack Notes – Complete Notes, Q&A & Exam Preparation

📘 Chapter Overview

In Class XI, different Python data types such as String, List, Set and Tuple were studied for handling values and representing collections of elements. A data structure is a mechanism used to store, organise and access data along with operations that can be efficiently performed on the data.

This chapter introduces Stack, its operations, implementation using Python and applications. It also explains arithmetic expression notations, conversion from infix to postfix notation and evaluation of postfix expressions.

📑 Table of Contents

1. 3.1 Introduction
2. 3.2 Stack
3. 3.2.1 Applications of Stack
4. 3.3 Operations on Stack
5. 3.3.1 PUSH and POP Operations
6. 3.4 Implementation of Stack in Python
7. Stack Functions in Python
8. Complete Stack Program
9. 3.5 Notations for Arithmetic Expressions
10. 3.6 Conversion from Infix to Postfix Notation
11. Algorithm 3.1
12. 3.7 Evaluation of Postfix Expression
13. Algorithm 3.2
14. Chapter Summary
15. Questions & Answers
16. Important Questions
17. Quick Revision
18. Textbook Exercise

3.1 Introduction

Python provides different data types for handling values. String, List, Set and Tuple are sequence data types that can represent collections of elements of the same type or different types.

Multiple data elements are grouped in a particular way for faster accessibility and efficient storage. Such grouping is called a data structure.

Meaning of Data Structure

A data structure defines a mechanism to store, organise and access data along with operations that can be efficiently performed on that data.

Examples from the Chapter

• String is a data structure containing a sequence of elements where each element is a character.
• List is a sequence data structure in which each element may be of different types.
• Operations such as reversal, slicing and counting can be applied on lists and strings.

Other Important Data Structures

Other important data structures in Computer Science include:

• Array
• Linked List
• Binary Trees
• Heaps
• Graph
• Sparse Matrix

Linear Data Structure

Stack and Queue are two popular data structures used in programming. Although they are not directly available in Python, their concepts are important because they are extensively used in a number of programming languages.

3.2 Stack

A stack can be understood using the example of a pile of books or a stack of plates. When another book or plate is added, it is placed only at the top. Similarly, when an object is removed, it is removed only from the top.

Adding or removing an object from the middle or bottom is inconvenient in a large pile. This arrangement of elements in a linear order is called a stack.

Definition of Stack

LIFO Principle

A stack follows the Last-In-First-Out (LIFO) principle. Therefore, the element inserted last is the first element to be removed.

3.2.1 Applications of Stack

Real-Life Applications

• Pile of clothes in an almirah
• Multiple chairs in a vertical pile
• Bangles worn on wrist
• Pile of boxes of eatables in pantry or on a kitchen shelf

Applications in Programming

1. Reversing a String

To reverse a string, the string is traversed from the last character to the first character. This can be done easily by putting the characters of the string in a stack.

2. Redo/Undo in Text or Image Editors

Text/image editors provide redo and undo options. The most recent editing is redone or undone when the corresponding icon is selected. A stack is used to keep track of changes made.

3. Browser Back Button

While browsing, web pages are accessed through links. Suppose a user moves from P1 to P2 and then P3. Clicking the BACK button once takes the user from P3 to P2, and another click takes the user to P1. The history of browsed pages is maintained as a stack.

4. Matching Parentheses

Arithmetic expressions may use parentheses to order the evaluation of operators. The compiler checks whether opening and closing parentheses are matched and properly nested. A stack is used to handle matching parentheses.

3.3 Operations on Stack

A stack implements a LIFO arrangement. Elements are added and deleted from one end only. This end is called the TOP of the stack.

The two fundamental operations performed on a stack are:

3.3.1 PUSH and POP Operations

PUSH

PUSH adds a new element at the TOP of the stack. It is an insertion operation.

Elements can be added until the stack becomes full. A stack is full when no more elements can be added. Trying to add an element to a full stack results in an exception called overflow.

POP

POP removes the topmost element of the stack. It is a deletion operation.

Elements can be deleted until the stack becomes empty. Trying to delete an element from an empty stack results in an exception called underflow.

Logical Sequence of the Textbook Example

The textbook illustrates a stack of numbered glasses. The sequence includes PUSH and POP operations in which the topmost glass is always affected.

In the illustrated sequence, POP removes 2, then 4, then 3 and finally 1 as the top element at each stage.

3.4 Implementation of Stack in Python

A stack is a linear and ordered collection of elements. A simple way to implement a stack in Python is by using the list data type.

Either side of the list can be fixed as TOP for inserting and removing elements. The chapter uses the rightmost end because Python’s built-in append() and pop() methods insert/delete elements at that end. Therefore, explicit declaration of TOP is not needed.

Operations Required in the Chapter Program

• Insert/delete elements (glasses)
• Check whether the stack is empty
• Find the number of elements in the stack
• Read the value of the topmost element

Stack Functions in Python

1. Creating an Empty Stack

An empty list named glassStack is created:

glassStack = list()

2. isEmpty()

The isEmpty function checks whether glassStack is empty. It returns True if the stack is empty and False otherwise.

def isEmpty(glassStack):
    if len(glassStack)==0:
        return True
    else:
        return False

3. opPush()

The opPush function inserts an element into the stack using append().

def opPush(glassStack,element):
    glassStack.append(element)

4. size()

The size function returns the number of elements in the stack by using Python’s len() function.

def size(glassStack):
    return len(glassStack)

5. top()

The top function reads the most recent element in glassStack. If the stack is empty, it displays Stack is empty and returns None.

def top(glassStack):
    if isEmpty(glassStack):
        print('Stack is empty')
        return None
    else:
        x =len(glassStack)
        element=glassStack[x-1]
        return element

6. opPop()

The opPop function removes and returns the topmost element. It first checks whether the stack is empty. The Python list method pop() removes the element from the end of the list.

def opPop(glassStack):
    if isEmpty(glassStack):
        print('underflow')
        return None
    else:
        return(glassStack.pop())

7. display()

The display function shows the contents of the stack.

def display(glassStack):
    x=len(glassStack)
    print("Current elements in the stack are: ")
    for i in range(x-1,-1,-1):
        print(glassStack[i])

💻 Complete Stack Program from the Chapter

After defining the functions, the chapter uses the following Python code to implement a stack of glasses.

glassStack = list() # create empty stack
#add elements to stack
element='glass1'
print("Pushing element ",element)
opPush(glassStack,element)
element='glass2'
print("Pushing element ",element)
opPush(glassStack,element)
#display number of elements in stack
print("Current number of elements in stack is",size(glassStack))
#delete an element from the stack
element=opPop(glassStack)
print("Popped element is",element)
#add new element to stack
element='glass3'
print("Pushing element ",element)
opPush(glassStack,element)
#display the last element added to the
#stack
print("top element is",top(glassStack))
#display all elements in the stack
display(glassStack)

#delete all elements from stack
while True:
    item=opPop(glassStack)
    if item == None:
        print("Stack is empty now")
        break
    else:
        print("Popped element is",item)

Output

Pushing element glass1
Pushing element glass2
Current number of elements in stack is 2
Popped element is glass2
Pushing element glass3
top element is glass3
Current elements in the stack are:
glass3
glass1
Popped element is glass3
Popped element is glass1
Underflow
Stack is empty now

📌 Important Points About Python Stack Implementation

• The stack is implemented using a Python list.
• append() adds an element at the end of the list.
• pop() removes an element from the end of the list.
• The chapter therefore does not require an explicit declaration of TOP.
• Python lists do not have a fixed size.
• The implemented stack will not become full unless there is no more space available in memory.
• Therefore, the chapter states that the implemented stack will not face an overflow condition under normal list-size operation.

3.5 Notations for Arithmetic Expressions

Arithmetic expressions are commonly written with operators between operands, such as x + y and 2 - 3 * y. Parentheses can be used to order evaluation in complex expressions. These expressions follow infix representation and are evaluated using the BODMAS rule.

Polish Notation

Polish mathematician Jan Lukasiewicz introduced a different way of representing arithmetic expressions in the 1920s, called Polish notation. In this notation, operators are written before their operands.

For example, x+y can be written as +xy. This is also called prefix notation because the operator is prefixed before the operands.

Reverse Polish Notation

By reversing this logic, operators can be placed after their operands. For example, x+y can be written as xy+. This is called reverse Polish notation or postfix notation.

Three Arithmetic Expression Notations

3.6 Conversion from Infix to Postfix Notation

Humans can easily evaluate an infix expression. For example, in x + y / z, the division operation is performed before addition because of operator precedence following BODMAS.

Prefix and postfix expressions do not have to deal with this precedence during evaluation because the operators are already positioned according to their order of evaluation. Hence, a single traversal from left to right is sufficient to evaluate the expression.

The chapter explains how an arithmetic expression written in infix notation can be converted into an equivalent postfix expression using a stack.

Role of Stack in Conversion

During conversion, a stack keeps track of the operators encountered in the infix expression. A string variable stores the equivalent postfix expression.

Algorithm 3.1: Conversion of Infix to Postfix

Detailed Step 4

1. If the character is a left parenthesis, PUSH it onto the Stack.
2. Else if the character is a right parenthesis, POP elements from the Stack and append them to postExp until the corresponding left parenthesis is popped. Discard both left and right parentheses.
3. Else if the character is an operator, compare its precedence with the operator at the top of the Stack.
4. If its precedence is lower than that of the operator at the top of the Stack, POP elements until an operator with precedence less than the current operator is encountered and append them to postExp before pushing the current operator onto the stack.
5. Otherwise, PUSH the operator onto the Stack.
6. If the character is an operand, append it to postExp.

📌 Example 3.1 – Infix to Postfix

The chapter converts the following infix expression into its equivalent postfix expression:

(x + y)/(z*8)

The stack is used to track the operators and parentheses, while a string variable contains the equivalent postfix expression.

Initially both are empty. Each character in the infix expression is processed from left to right and the appropriate action is performed according to the algorithm. After all characters are processed, the string contains the equivalent postfix expression.

3.7 Evaluation of Postfix Expression

A stack can also be used to evaluate an expression written in postfix notation. For simplification, the chapter assumes that operators used in expressions are binary operators.

Algorithm 3.2: Evaluation of Postfix Expression

1. Step 1: INPUT postfix expression in a variable, say postExp.
2. Step 2: For each character in postExp, repeat Step 3.
3. Step 3: If the character is an operand, PUSH the character onto the Stack.
4. Else, POP two elements from the Stack, apply the operator on the popped elements and PUSH the computed value onto the Stack.
5. Step 4: If the Stack has a single element, POP the element and OUTPUT it as the net result.
6. Otherwise, OUTPUT “Invaild Postfix expression” as given in the textbook.

📌 Example 3.2 – Evaluation of Postfix Expression

The chapter demonstrates evaluation of the postfix expression:

7 8 2 * 4 / +

The stack-based procedure PUSHes operands, POPs two elements when an operator occurs, applies the operator and PUSHes the computed result back onto the Stack.

📚 Chapter Summary

• Stack is a data structure in which insertion and deletion are done from one end only, usually referred to as TOP.
• Stack follows the LIFO principle, in which the element inserted last is the first one to be removed.
• PUSH and POP are the two basic operations performed on a stack for insertion and deletion respectively.
• Trying to POP an element from an empty stack results in the special condition called underflow.
• In Python, a list is used for implementing a stack.
• The built-in functions append() and pop() are used for insertion and deletion respectively.
• Because of the way the Python list is used in this implementation, no explicit declaration of TOP is needed.
• An arithmetic expression can be represented in Infix, Prefix or Postfix notation.
• Infix notation places binary operators between operands.
• A single traversal from left to right is sufficient to evaluate Prefix/Postfix expressions because operators are correctly placed according to their order of precedence.
• Stack is commonly used to convert an Infix expression into equivalent Prefix/Postfix notation.
• During conversion of an Infix notation to its equivalent Prefix/Postfix notation, only operators are PUSHed onto the Stack.
• When evaluating a Postfix expression using Stack, only operands are PUSHed onto it.

❓ Questions & Answers

1-Mark Questions

2-Mark Questions

3-Mark Questions

4/5-Mark Questions

📝 Important Questions

1 Mark

1. Define stack.
2. What is LIFO?
3. What is TOP?
4. Define PUSH operation.
5. Define POP operation.
6. What is overflow?
7. What is underflow?
8. What is infix notation?
9. What is prefix notation?
10. What is postfix notation?

2 Marks

1. Differentiate between PUSH and POP operations.
2. Differentiate between overflow and underflow.
3. Mention applications of stack in programming.
4. Explain the use of a stack for matching parentheses.
5. Explain the use of a stack in browser history.

3 Marks

1. Explain the applications of stack.
2. Explain Infix, Prefix and Postfix notations with examples.
3. Explain how a stack is implemented using a Python list.
4. Explain the role of stack in infix-to-postfix conversion.

4/5 Marks

1. Write the functions required to implement a stack in Python.
2. Write a program to implement the stack of glasses shown in the chapter.
3. Explain Algorithm 3.1 for converting infix to postfix notation.
4. Explain Algorithm 3.2 for evaluating postfix expressions.
5. Show the stack-based evaluation process of the postfix expression given in the chapter.
6. Write a program to reverse a string using stack.

⚡ Quick Revision

glassStack = list()

glassStack.append(element)

glassStack.pop()

len(glassStack)

🔄 Final Revision Flow

📖 Textbook Exercise

The following questions are the exercise questions provided at the end of the uploaded chapter.

1. State TRUE or FALSE

1. Stack is a linear data structure.
2. Stack does not follow LIFO rule.
3. PUSH operation may result into underflow condition.
4. In POSTFIX notation for expression, operators are placed after operands.

2. Find the output of the following code

(a)

result=0
numberList=[10,20,30]
numberList.append(40)
result=result+numberList.pop()
result=result+numberList.pop()
print(“Result=”,result)

(b)

answer=[]; output=''
answer.append('T')
answer.append('A')
answer.append('M')
ch=answer.pop()
output=output+ch
ch=answer.pop()
output=output+ch
ch=answer.pop()
output=output+ch
print(“Result=”,output)

3. String Reversal

Write a program to reverse a string using stack.

4. Matching Parentheses

For the arithmetic expression below, show the step-by-step process for matching parentheses using stack data structure:

((2+3)*(4/2))+2

5. Evaluate Postfix Expressions

Evaluate the following postfix expressions while showing the status of the stack after each operation, given:

A=3, B=5, C=1, D=4

1. A B + C *
2. A B * C / D *

6. Convert Infix to Postfix

Convert the following infix notations to postfix notations, showing stack and string contents at each step.

1. A + B - C * D
2. A * (( C + D)/E)

7. Stack Program for Odd Numbers

Write a program to create a Stack for storing only odd numbers out of all the numbers entered by the user. Display the content of the Stack along with the largest odd number in the Stack.

🎯 Last-Minute Exam Revision