Stacks and Queues: Two Marks Important Questions and Answers

Data Structures using C ++

Chapter 4: Stacks and Queues

Two Marks Questions with Answers

1. Give applications of stacks and give example for one of them.

Answer:

Applications of stack ‒

1. The stack is used to convert one expression to another form.

2. It is used to evaluate an expression.

3. For checking well formedness of the parenthesis the stack is used.

4. The stack is also used for reversing the string.

5. The stack is used to convert decimal number to its equivalent binary form.

For example: The stack is used to evaluate the postfix expression. The algorithm for the same is as given below ‒

1. Read the postfix expression from left to right.

2. If the input symbol read is operand then push it onto the stack.

3. If the operator is read then POP two operands and perform arithmetic operations if operator is ‒

+           then result = operand1 + operand2

‒           then result = operand1 ‒ operand2

*          then result = operand1 * operand 2

/           then result = operand1 / operand 2

4. Push the result onto the stack.

5. Repeat steps 1‒ 4 till the postfix expression is not over. For example : Consider the postfix expression 12+34*+

We will read 1 then 2 and push them onto the stack. When + operator is read pop 2 and 1 perform 1+2, the result 3 is pushed onto the stack. Now read 3 and 4 then push onto the stack when * is read pop 4 and 3. Perform 3*4, push 12 onto the stack. Now push 12 onto the stack. The stack contains 3 and 12. When the next character + is read then we pop 12 and 3 to perform 12+3. The result will be 15.

2. List the characteristics of the stack.

Answer:

1. Insertion and deletion can be made by one end only. Hence the element inserted last will be first one to come out. Hence sometimes it is called LIFO.

2. Stacks are useful for evaluating an expression.

3. Stacks can store the functions calls.

3. Write the role of stack in function call.

Answer:

The stack is an useful data structure for handling the recursive function calls. When a recursive call is encountered, the status of call is pushed onto the stack. And at the return of the call the stack is popped off. Thus execution of recursive statements is done with the help of stack.

4. List few applications of queues.

Answer:

Application of queues ‒

1. In operating system for scheduling the jobs, priority queues are used.

2. For categorizing data.

3. In simulation and modeling queues are used.

5. How is data sorted in QUEUE structure ?

Answer:

 Based on the priority of execution the data can be sorted in the Queue structure. Such type of queue is called priority queue.

6. What is meant by underflow and overflow condition in a stack ?

Answer:

The underflow is a situation in which the pop operation is performed on the stack which is empty. The overflow is a situation in which the push operation is performed on the stack which is full.

7.  What is Last‒In‒First‒Out strategy? Which data structure follow this strategy?

Answer:

In the Last In First Out strategy we insert the element in the data structure lastly and while removing the elements from this data structure, the element which is inserted lastly will get removed first. The stalk data structure makes use of Last In First Out (LIFO) data structures.

8. What is FIFO data structure ?

Answer:

The FIFO stands for First In First Out. This property is satisfied by queue. Hence queue is called FIFO data structure.

9. Evaluate the value of expression ab+c*d‒ using stack

Ans. :

10. Consider a sequence of input 1, 2, 3, 4, 5. How will you make use of stack and queue both in order to get the sequence 3, 4, 5, 2, 1.

Answer:

Step 1: Consider 1, 2, 3, 4, 5 on to the stack.

Step 2: POP( ), POP( ), POP( ) Insert the element in the queue after each POP().

Step 3: Delete queue elements and push them onto the stack

Step 4: POP all the elements from the stack and print, 3, 4, 5, 2, 1.

11. What is the time complexity of push() and POP() operation ?

Answer:

Push operation ‒ O(1).

Pop operation O(1).

12. Consider the following code,

Q.front = ‒1;

Q.rear = ‒1;

insert(3);

insert(5);

insert(9);

cout<<deleteq();

insert(12);

insert(40);

cout<<deleteq( );

cout<<deleteq():

insert(11);

insert(10);

After executing above code, how many elements would remain in queue ?

Answer:

13. Write a short note on queue.

OR

What do you mean by queue ADT ?

Answer:

• Queue is a linear data structure in which the insertion of element is from one end called rear and deletion of element is from the other end called front.

• C representation

struct queue

{

   Int que[size];

   int front;

   int rear:

}Ο;