Question 1

For queues, FIFO stands for:

Accepted Answer

First In First Out

Question 2

In a stack, Insertion is done at Top. From which end does deletion take place ?

Accepted Answer

Top

Question 3

In stack, LIFO stands for:

Accepted Answer

Last In First Out

Question 4

In a queue, if front is equal to rear, it means that:

Accepted Answer

Queue has only one element

Question 5

Which of the following is NOT an application of Stack:

Accepted Answer

Handling of Interrupts

Question 6

State TRUE or FALSE for the following cases:
a) Stack is a linear data structure
b) Stack does not follow LIFO rule
c) PUSH operation may result into underflow condition
d) In POSTFIX notation for expression, operators are placed after operands

Accepted Answer

a) TRUE. Stack is a linear data structure as elements are arranged sequentially.
b) FALSE. Stack follows LIFO (Last In First Out) rule.
c) FALSE. PUSH operation may result in overflow condition, not underflow. Underflow occurs during POP when stack is empty.
d) TRUE. In postfix notation, operators come after their operands. — a) Stack elements are arranged linearly.
b) Stack follows LIFO, so statement is false.
c) PUSH adds element; underflow occurs on POP when empty.
d) Postfix places operators after operands.

Question 7

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)

Accepted Answer

a) Initially, result=0, numberList=[10,20,30]
numberList.append(40) makes numberList=[10,20,30,40]
numberList.pop() removes 40 and returns it, so result=0+40=40
numberList.pop() removes 30 and returns it, so result=40+30=70
Output: Result= 70

b) answer=[]; output=""
answer.append('T') -> ['T']
answer.append('A') -> ['T','A']
answer.append('M') -> ['T','A','M']
ch=answer.pop() -> 'M', output=""+"M"="M"
ch=answer.pop() -> 'A', output="M"+"A"="MA"
ch=answer.pop() -> 'T', output="MA"+"T"="MAT"
Output: Result= MAT — a) The pop() method removes the last element added (LIFO). Adding 40, then popping twice removes 40 and 30.
b) Stack operations append and pop reverse the order of letters, so output is 'MAT'.

Question 8

Write a program to reverse a string using stack.

Accepted Answer

Program to reverse a string using stack:

```python
# Function to reverse string using stack

def reverse_string(s):
    stack = []
    # Push all characters to stack
    for char in s:
        stack.append(char)
    # Pop all characters from stack and form reversed string
    reversed_str = ''
    while stack:
        reversed_str += stack.pop()
    return reversed_str

# Example usage
input_str = 'HELLO'
print('Original String:', input_str)
print('Reversed String:', reverse_string(input_str))
```

Output:
Original String: HELLO
Reversed String: OLLEH — The program uses a list as a stack. Each character of the string is pushed onto the stack. Then characters are popped from the stack to form the reversed string, demonstrating LIFO behavior.

Question 9

For the following arithmetic expression:
$$((2+3)*(4/2))+2$$
Show step-by-step process for matching parentheses using stack data structure.

Accepted Answer

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

Step-by-step process for matching parentheses using stack:

1. Initialize an empty stack.
2. Scan the expression from left to right.
3. When an opening parenthesis '(' is encountered, push it onto the stack.
4. When a closing parenthesis ')' is encountered, check the stack:
   - If stack is empty, parentheses are not balanced.
   - Else pop the top element from the stack.
5. After scanning entire expression, if stack is empty, parentheses are balanced; otherwise not.

Detailed steps:

Index: Character - Stack status
0: '(' - push '(' -> stack: ['(']
1: '(' - push '(' -> stack: ['(', '(']
2: '2' - ignore (not parenthesis)
3: '+' - ignore
4: '3' - ignore
5: ')' - pop '(' -> stack: ['(']
6: '*' - ignore
7: '(' - push '(' -> stack: ['(', '(']
8: '4' - ignore
9: '/' - ignore
10: '2' - ignore
11: ')' - pop '(' -> stack: ['(']
12: ')' - pop '(' -> stack: []
13: '+' - ignore
14: '2' - ignore

At end, stack is empty, so parentheses are matched correctly. — Using stack to match parentheses ensures every opening '(' has a corresponding closing ')'. Pushing on '(' and popping on ')' helps verify balanced parentheses.

Question 10

Evaluate following postfix expressions while showing status of stack after each operation given A=3, B=5, C=1, D=4
a) A B + C *
b) A B * C / D *

Accepted Answer

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

Evaluate postfix expressions stepwise:

a) A B + C *
Stack operations:
- Push A(3): stack=[3]
- Push B(5): stack=[3,5]
- '+' operator: pop 5 and 3, compute 3+5=8, push 8: stack=[8]
- Push C(1): stack=[8,1]
- '*' operator: pop 1 and 8, compute 8*1=8, push 8: stack=[8]

Final result: 8

b) A B * C / D *
Stack operations:
- Push A(3): stack=[3]
- Push B(5): stack=[3,5]
- '*' operator: pop 5 and 3, compute 3*5=15, push 15: stack=[15]
- Push C(1): stack=[15,1]
- '/' operator: pop 1 and 15, compute 15/1=15, push 15: stack=[15]
- Push D(4): stack=[15,4]
- '*' operator: pop 4 and 15, compute 15*4=60, push 60: stack=[60]

Final result: 60 — Postfix evaluation uses a stack:
- Push operands.
- On operator, pop required operands, compute, push result.
- Final stack top is result.

Question 11

Convert the following infix notations to postfix notations, showing stack and string contents at each step.
a) A + B - C * D
b) A * ((C + D)/E)

Accepted Answer

a) Convert infix: A + B - C * D to postfix

Operator precedence: * > + and -

Stepwise:

Expression: A + B - C * D

Initialize stack: empty
Postfix string: empty

1. Read 'A': operand, add to postfix -> postfix: A
2. Read '+': stack empty, push '+' -> stack: ['+']
3. Read 'B': operand, add to postfix -> postfix: AB
4. Read '-': '-' has same precedence as '+', so pop '+' from stack to postfix -> postfix: AB+
Push '-' -> stack: ['-']
5. Read 'C': operand, add to postfix -> postfix: AB+C
6. Read '*': '*' has higher precedence than '-', push '*' -> stack: ['-', '*']
7. Read 'D': operand, add to postfix -> postfix: AB+CD

End of expression: pop all operators from stack:
Pop '*': postfix: AB+CD*
Pop '-': postfix: AB+CD*-

Final postfix: AB+CD*-

b) Convert infix: A * ((C + D)/E)

Stepwise:

Expression: A * ((C + D)/E)

Stack: empty
Postfix: empty

1. Read 'A': operand, postfix: A
2. Read '*': stack empty, push '*' -> stack: ['*']
3. Read '(': push '(' -> stack: ['*', '(']
4. Read '(': push '(' -> stack: ['*', '(', '(']
5. Read 'C': operand, postfix: AC
6. Read '+': push '+' (stack top is '(') -> stack: ['*', '(', '(', '+']
7. Read 'D': operand, postfix: ACD
8. Read ')': pop operators until '(':
Pop '+': postfix: ACD+
Pop '(': remove
Stack: ['*', '(']
9. Read '/': push '/' (stack top is '(') -> stack: ['*', '(', '/']
10. Read 'E': operand, postfix: ACD+E
11. Read ')': pop operators until '(':
Pop '/': postfix: ACD+E/
Pop '(': remove
Stack: ['*']

End of expression: pop remaining operators:
Pop '*': postfix: ACD+E/*

Final postfix: ACD+E/* — Use operator precedence and associativity rules.
Push '(' on stack.
Pop operators when encountering ')' or lower precedence operator.
Operands go directly to postfix.

This method ensures correct postfix conversion.

Question 12

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. (Hint. Keep popping out the elements from stack and maintain the largest element retrieved so far in a variable. Repeat till Stack is empty)

Accepted Answer

Program to store only odd numbers in stack and find largest odd number:

```python
# Initialize empty stack
stack = []

# Input numbers from user
n = int(input('Enter number of elements: '))
print('Enter numbers:')
for _ in range(n):
    num = int(input())
    if num % 2 != 0:  # Check if odd
        stack.append(num)

# Display stack content
print('Stack content (odd numbers):', stack)

# Find largest odd number by popping
if not stack:
    print('No odd numbers entered.')
else:
    largest = stack.pop()
    while stack:
        val = stack.pop()
        if val > largest:
            largest = val
    print('Largest odd number in stack:', largest)
```

Explanation:
- Only odd numbers are pushed onto stack.
- Then stack is popped completely to find largest odd number.
- If no odd numbers, appropriate message is shown. — The program filters odd numbers and stores them in stack.
Popping all elements allows comparison to find the largest odd number.
This demonstrates stack usage and conditional logic.

Question 13

Which of the following best defines a data structure in Computer Science?

Accepted Answer

A mechanism to store, organise and access data along with operations that can be efficiently performed on the data — A data structure is a mechanism that stores, organizes, and provides access to data efficiently, along with operations to process the data. This is fundamental in computer science for managing data effectively.

Question 14

Identify the data structure that follows the Last-In-First-Out (LIFO) principle and allows insertion and deletion from only one end called 'top'.

Accepted Answer

Stack — A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, where elements are inserted and deleted only from the top end.

Question 15

In the context of stack operations, what is the result of trying to remove an element from an empty stack called?

Accepted Answer

Underflow — Underflow occurs when a pop operation is attempted on an empty stack, meaning there are no elements to remove.

Stack

Stack — Study Notes

3.1 INTRODUCTION

3.2 STACK

3.2.1 APPLICATIONS OF STACK

Practice Questions — Stack

All 13 Chapters in Computer Science