Stacks and Queues in List

This page contains the CBSE Computer Science with Python class 12 Unit-2 chapter 2 Stacks and Queues in List. You can find the solutions for chapter 2 of CBSE class 12 Computer Science with Python Exercise. So is the case if you are looking for CBSE class 12 Computer Science with Python related topic Stacks and Queues in List questions and answers for the Exercise.
Buy Class 12 CBSE Computer Science with Python Books NOW!
Exercise
Question 1
1. Expand the following:
(i)
LIFO
(ii)
FIFO
Answer 1
(i)
LIFO: Last In First Out
(ii)
FIFO: First In First Out
Question 2
2. What is stack?
Answer 2
A stack is a linear data structure that follows LIFO order.
Insertion and deletion are done only at one end called the TOP.
Main operations are PUSH (insert) and POP (delete).
Question 3
3. What is Queue?
Answer 3
A queue is a linear data structure that follows FIFO order.
Insertion is done at the REAR and deletion is done from the FRONT.
Question 4
4. What are all operations possible in data structure?
Answer 4
Common operations possible on data structures are:
1.
Traversal: visiting each element one by one.
2.
Insertion: adding a new element at a required position.
3.
Deletion: removing an element from a required position.
4.
Searching: finding whether an element is present (and its position).
5.
Sorting: arranging elements in ascending or descending order.
6.
Merging: combining two similar data structures into one.
Question 5
5. Give one example of infix expression.
Answer 5
Example of infix expression: A + B
Question 6
6. Give one example of postfix expression.
Answer 6
Example of postfix expression: AB+
Question 7
7. Give one example of prefix expression.
Answer 7
Example of prefix expression: +AB
Question 8
8. Convert (A+B)*C into postfix form.
Answer 8
Postfix form of (A+B)*C is AB+C*.
Question 9
9. Evaluate using stack: 10, 3, *, 30, 2, *, –
Answer 9
Postfix evaluation:
•
10 3 * = 30
•
30 2 * = 60
•
30 60 – = -30
Final Answer: -30
Question 10
10. Convert following infix expressions into Postfix notation:
(a)
(A+B)
(b)
P+Q*(R-S)
(c)
(True And False) || (False And True)
Answer 10
(a)
AB+
(b)
PQRS-*+
(c)
True False And False True And ||
Question 11
11. Evaluate the following Postfix Expressions:
(a)
20,8,4,/,2,3,+,*,-
(b)
15,3,2,+,/,7,+,2,*
(c)
False, Not, True, And, True, False, Or, And
(d)
True, False, Not, And, False, True, Or, And
Answer 11
(a)
8 4 / = 2
2 3 + = 5
2 5 * = 10
20 10 – = 10
(b)
3 2 + = 5
15 5 / = 3
3 7 + = 10
10 2 * = 20
(c)
False Not = True
True And True = True
True False Or = True
True And True = True
(d)
False Not = True
True And True = True
False True Or = True
True And True = True
Question 12
12. Write the push operation of stack containing names using class.
Answer 12
# Push operation for stack of names (Python 2)
class NameStack(object):
    def __init__(self):
        self.stk = []

    def push(self, name):
        # insert at top of stack
        self.stk.append(name)

    def show(self):
        print "Stack:", self.stk
Question 13
13. Write the pop operation of stack containing numbers using class.
Answer 13
# Pop operation for stack of numbers (Python 2)
class NumberStack(object):
    def __init__(self):
        self.stk = []

    def pop_num(self):
        if len(self.stk) == 0:
            print "Stack Underflow"
            return None
        return self.stk.pop()
Question 14
14. Write the insertion operation of queue containing character using class.
Answer 14
# Insertion (enqueue) in queue of characters (Python 2)
class CharQueue(object):
    def __init__(self):
        self.q = []

    def insert(self, ch):
        # insert at rear
        self.q.append(ch)
Question 15
15. Write the deletion operation of queue containing numbers using class.
Answer 15
# Deletion (dequeue) in queue of numbers (Python 2)
class NumberQueue(object):
    def __init__(self):
        self.q = []

    def delete(self):
        if len(self.q) == 0:
            print "Queue Underflow"
            return None
        return self.q.pop(0)
Question 16
16. Write any two example of stack operation.
Answer 16
Any two stack operations are:
1.
PUSH: insert an element at TOP
2.
POP: delete an element from TOP
Question 17
17. Write any two example of pop operation.
Answer 17
Examples of pop operation:
1.
Stack before pop: [10, 20, 30], after pop: [10, 20], popped element: 30
2.
Stack before pop: [‘A’, ‘B’], after pop: [‘A’], popped element: ‘B’
Question 18
18. Write an algorithm to evaluate postfix expression.
Answer 18
1.
Create an empty stack.
2.
Scan postfix expression from left to right.
3.
If token is operand, PUSH it to stack.
4.
If token is operator, POP two operands (op2 then op1), evaluate op1 operator op2, PUSH result.
5.
Repeat until expression ends.
6.
Final value at top of stack is the answer.
Question 19
19. Write an algorithm to convert infix to postfix.
Answer 19
1.
Create empty operator stack and empty postfix output.
2.
Scan infix expression from left to right.
3.
If token is operand, add it to postfix output.
4.
If token is ‘(‘, PUSH it to stack.
5.
If token is ‘)’, POP and append until ‘(‘ is found; remove ‘(‘.
6.
If token is operator, POP operators with higher/equal precedence, then PUSH current operator.
7.
After scan, POP all remaining operators to postfix output.
Question 20
20. Write an algorithm to implement push operation.
Answer 20
1.
START
2.
Input ITEM to be pushed.
3.
If stack is full, print OVERFLOW and STOP.
4.
Set TOP = TOP + 1.
5.
STACK[TOP] = ITEM.
6.
STOP
Question 21
21. Write an algorithm to implement pop operation.
Answer 21
1.
START
2.
If TOP = -1, print UNDERFLOW and STOP.
3.
ITEM = STACK[TOP].
4.
Set TOP = TOP – 1.
5.
Return/print ITEM.
6.
STOP
Question 22
22. Write an algorithm to implement insertion operation of queue.
Answer 22
1.
START
2.
Input ITEM to be inserted.
3.
If queue is full, print OVERFLOW and STOP.
4.
If queue is empty, set FRONT = 0 and REAR = 0, else REAR = REAR + 1.
5.
QUEUE[REAR] = ITEM.
6.
STOP
Question 23
23. Write an algorithm to implement deletion operation of queue.
Answer 23
1.
START
2.
If queue is empty, print UNDERFLOW and STOP.
3.
ITEM = QUEUE[FRONT].
4.
If FRONT = REAR, set FRONT = REAR = -1, else FRONT = FRONT + 1.
5.
Return/print ITEM.
6.
STOP
Question 24
24. Write a function to push any student’s information to stack.
Answer 24
# Define Student class (Python 2)
class Student(object):
    def __init__(self, roll_no, name, marks):
        self.roll_no = roll_no
        self.name = name
        self.marks = marks

    def __str__(self):
        return "Roll: %d, Name: %s, Marks: %d" % (self.roll_no, self.name, self.marks)

# Function to push student to stack
def push_student(stack, student):
    stack.append(student)
Usage Example:
st_stack = []
push_student(st_stack, Student(1, "Aman", 78))
push_student(st_stack, Student(2, "Neha", 92))
for s in st_stack:
    print s
# Roll: 1, Name: Aman, Marks: 78
# Roll: 2, Name: Neha, Marks: 92
Question 25
25. Write a function to add any customer’s information to queue.
Answer 25
# Define Customer class (Python 2)
class Customer(object):
    def __init__(self, cust_id, cust_name, phone):
        self.cust_id = cust_id
        self.cust_name = cust_name
        self.phone = phone

    def __str__(self):
        return "ID: %s, Name: %s, Phone: %s" % (self.cust_id, self.cust_name, self.phone)

# Function to add customer to queue
def add_customer(queue, customer):
    queue.append(customer)
Usage Example:
cust_q = []
add_customer(cust_q, Customer("C101", "Riya", "9876543210"))
add_customer(cust_q, Customer("C102", "Kabir", "9123456780"))
for c in cust_q:
    print c
# ID: C101, Name: Riya, Phone: 9876543210
# ID: C102, Name: Kabir, Phone: 9123456780