# DST Unit 5 – Stack and Queue most asked questions

## Topic : Stack (Key Note and Questions)

Key Note:

• Stack is a linear data structure that follows LIFO principles.
• LIFO stands for Last In First Out
• We can implement stack using linked list and array.
• Some Application of Data Structure are Infix to Postfix conversion, Infix to Prefix conversion, Postfix and prefix evaluation etc.

### Questions

1. What is stack? Explain with suitable example with all its application.
2. Implement stack with singly linked list.
3. What is push and pop operation of stack? Write the algorithm for push and pop operation.
4. Write a program in c for array implementation of stack.
5. Write a program in c for linked list implementation of stack.
6. What is infix, prefix and postfix expression? Explain with example.
7. Write down an algorithm to evaluate the infix expression.
8. Write down an algorithm to evaluate the postfix expression.
9. Write down an algorithm to evaluate the Prefix expression.
10. Convert following infix expression into postfix expression A+(B*C+D)/E
11. Write an algorithm to convert a postfix expression into an infix expression. Consider the following arithmetic expression in postfix notation: 752+*415-/-
12. Write an algorithm to convert Infix expression to Prefix. Convert this expression into prefix
13. What is recursion? Write its principle. Explain with the help of example.
14. Explain the types of recursion.
15. Explain Tower of Hanoi with example.
16. Write the recursive algorithm for solving the problem of Tower of Hanoi and also explain its complexity. Illustrate the solution for four disks and three pegs.

## Topic : Queue (Key Note and Questions)

Key Note:

• Queue is a linear data structure that follows FIFO principles.
• FIFO stands for First In First Out.
• Queue can be implemented using Array and Linked List.
• Application of  Queue is, Queue is helpful in CPU scheduling, Disk Scheduling, Handling of interrupts in real-time systems etc

### Questions

1. Write a note on queue. Explain its various operations.
2. What is circular queue? Write a C code to insert an element in circular queue. Write all the condition for overflow.
3. Write a C program to implement the array representation of circular queue.
4. Explain queue and priority queue. Also write its types.