Q1. Which of the following data structures follows the LIFO principle?
(a) Queue
(b) Stack
(c) Linked List
(d) Tree
Q2. In a stack, the end from which elements are inserted or deleted is called:
(a) Front
(b) Rear
(c) TOP
(d) Base
Q3. Assertion (A): Trying to perform POP operation on an empty stack results in underflow.
Reason (R): A stack is empty when it contains no elements and deletion is not possible.
(a) Both A and R are true and R is the correct explanation of A.
(b) Both A and R are true but R is not the correct explanation of A.
(c) A is true but R is false.
(d) A is false but R is true.
Q4. Which built-in method of Python list is used to implement the PUSH operation on a stack?
(a) pop()
(b) append()
(c) insert()
(d) remove()
Q5. Assertion (A): Stack is a linear data structure.
Reason (R): Elements in a stack are organised in a sequence and operations are performed at one end only.
(a) Both A and R are true and R is the correct explanation of A.
(b) Both A and R are true but R is not the correct explanation of A.
(c) A is true but R is false.
(d) A is false but R is true.
Q6. In the expression x + y * z, which notation places the operators after the operands?
(a) Infix
(b) Prefix
(c) Postfix
(d) None of these
Q7. The condition when no more elements can be added to a stack is called:
(a) Underflow
(b) Overflow
(c) Empty stack
(d) Full stack
Q8. Which of the following is NOT an application of stack?
(a) Reversing a string
(b) Matching parentheses
(c) Browser history using BACK button
(d) CPU scheduling using Round Robin
Q9. While converting an infix expression to postfix using a stack, which elements are pushed onto the stack?
(a) Operands only
(b) Operators and parentheses only
(c) Both operands and operators
(d) None of these
Q10. In postfix notation, the expression x + y is written as:
(a) +xy
(b) xy+
(c) x+y
(d) yx+
Q1. Define stack as a data structure. State the principle it follows.
Q2. Differentiate between PUSH and POP operations on a stack.
Q3. What is the output of the following code fragment?
python
stack = []
stack.append(10)
stack.append(20)
print(stack.pop())
print(len(stack))
Q4. What is underflow condition in a stack? When does it occur?
Q5. Write the postfix form of the infix expression (A + B) * C.
Q6. State two real-life examples of stack from the chapter.
Q1. Write the Python functions isEmpty() and opPush() for stack implementation using list as per NCERT.
Q2. Identify the error in the following code and correct it:
python
def top(glassStack):
if len(glassStack) == 0:
return None
else:
return glassStack[0] # Error here
Q3. Show the step-by-step conversion of the infix expression A + B * C to postfix notation using stack. Show stack and postfix string after each step.
Q4. Evaluate the postfix expression 7 8 2 * 4 / + showing the status of the stack after each operation.
Q5. What will be the output of the following code? Explain briefly.
python
answer = []
answer.append('T')
answer.append('A')
answer.append('M')
output = ''
while answer:
output = output + answer.pop()
print(output)
Q1. Write a complete Python program to create a stack that stores only odd numbers entered by the user. The program should allow pushing elements, display the stack contents from top to bottom, and find the largest odd number in the stack.
Q2. Explain Algorithm 3.2 for evaluation of a postfix expression. Perform a dry-run of the expression 5 6 2 * + 4 - using a trace table showing stack contents after each step.
Q3. Write a complete Python program that implements a stack using list and provides the following menu-driven operations: PUSH, POP, display stack, check if empty, and find size of stack. Use the functions as defined in the chapter.
Case 1: A web browser maintains the history of visited pages using a stack so that the BACK button can take the user to the previously visited page. The current page is always at the TOP of the stack.
(a) Which data structure is used and why?
(b) What operation is performed when a user clicks the BACK button?
(c) If the stack is empty and the user clicks BACK, what condition occurs?
(d) Give one more real-life application of stack mentioned in the chapter that works on similar principle.
Case 2: A compiler uses stack to check whether parentheses in an arithmetic expression are correctly matched while converting the expression from infix to postfix notation.
(a) Which elements are pushed onto the stack during infix to postfix conversion?
(b) What action is taken when a right parenthesis is encountered?
(c) Why is stack suitable for this matching process?
(d) Name the notation in which operators are placed before the operands.
Q1. (b) Stack
Q2. (c) TOP
Q3. (a) Both true and R explains A
Q4. (b) append()
Q5. (a) Both true and R explains A
Q6. (c) Postfix
Q7. (b) Overflow
Q8. (d) CPU scheduling using Round Robin
Q9. (b) Operators and parentheses only
Q10. (b) xy+
Q1. Stack is a linear data structure in which insertion and deletion of elements is done from one end called TOP. It follows LIFO principle.
Q2. PUSH inserts an element at TOP (insertion operation). POP removes the topmost element (deletion operation).
Q3. Output:
20
1
(Explanation: 20 is popped and one element remains.)
Q4. Underflow occurs when POP is attempted on an empty stack.
Q5. AB+C*
Q6. Pile of plates/books and browser history using BACK button.
Q1.
```python
def isEmpty(glassStack):
if len(glassStack) == 0:
return True
else:
return False
def opPush(glassStack, element):
glassStack.append(element)
``
Q2. Error:glassStack[0]returns bottom element instead of TOP.
Correction:return glassStack[len(glassStack)-1]orreturn glassStack[-1]`.
Q3. Steps (stack shown):
A → stack: empty, post: A
+ → stack: +, post: A
B → stack: +, post: AB
→ stack: * (after pop +), post: AB+
C → stack: , post: AB+C
Final postfix: AB+C*
Q4. Trace: 7 pushed; 8 pushed; 2 pushed; * → 16 pushed; 4 pushed; / → 4 pushed; + → 11 (final result 11).
Q5. Output: MAT
(Explanation: Characters are pushed then popped in LIFO order.)
Q1.
```python
stack = []
def isEmpty(s):
return len(s) == 0
def push(s, ele): if ele % 2 != 0: s.append(ele)
def display(s): for i in range(len(s)-1, -1, -1): print(s[i])
def largestOdd(s): if isEmpty(s): return None max_odd = 0 while s: val = s.pop() if val > max_odd: max_odd = val return max_odd
``
Q2. Trace table for5 6 2 * + 4 -`:
5 → [5]
6 → [5,6]
2 → [5,6,2]
* → [5,12]
+ → [17]
4 → [17,4]
- → [13]
Result = 13
Q3. Complete menu-driven program using chapter functions (isEmpty, opPush, opPop, size, top, display) with while loop for menu.
Case 1: (a) Stack (LIFO for last visited page) (b) POP operation (c) Underflow (d) Pile of plates/books or undo/redo in editors.
Case 2: (a) Operators and parentheses (b) POP until matching left parenthesis (c) LIFO helps in matching nested pairs correctly (d) Prefix notation.
All questions are answerable from the NCERT chapter text. Reviewed by GFIS faculty.