Solution

top == SIZE-1 As SIZE-1 is the last index of the array and if top is pointing to it that means there is no room to insert any other element hence this an overflow condition

and top == -1 0th index is 1st index where we can insert the 1st element in stack, if top’s value is -1 means there is no element present in the stack anymore and this is an underflow condition.

Solution

Time complexity to push an element into a stack implemented using an array is O(1).

Time complexity to push an element into a stack implemented using a linked list is O(1).

Hence the given statement is wrong

Solution

Since the stack data structure follows LIFO order. When we pop() items from stack, they are popped in reverse order of their insertion (or push())

Solution

A queue is a data structure where you do all insertions and deletions at rear and front respectively.

Solution

1st P1:

2 dequeue & 2 push:

1 pop & 1 enqueue:

2nd P1:

3rd P1:

Hence ‘e’ will be at top.

Solution

The queue data structure is FIFO i.e. first in first out and hence the output will be zyxw.

Solution

+ a * - * b c * / d ^ e f g h

Explanation:

Algorithm for Prefix to Postfix:

• Read the Prefix expression in reverse order (from right to left)
• If the symbol is an operand, then push it onto the Stack
• If the symbol is an operator, then pop two operands from the Stack
  

  Create a string by concatenating the two operands and the operator after them.
  

  string = operand1 + operand2 + operator
  

  And push the resultant string back to Stack

• Repeat the above steps until the end of the Prefix expression.

Solution

Reverse infix: ) E - D ^ C ( * B + A

Reverse bracket: ( E - D ^ C ) * B + A

Prefix expression: +A*B-^CDE

Explanation:

• Step 1: Reverse the infix expression. Note while reversing each ‘(‘ will become ‘)’ and each ‘)’ becomes ‘(‘.
• Step 2: Obtain the postfix expression of the modified expression
• Step 3: Reverse the postfix expression.

Algorithm for postfix evaluation:

1. Scan the infix expression from left to right.

2. If the scanned character is an operand, output it.

3. Else,

…..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.

…..3.2 Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)

4. If the scanned character is an ‘(‘, push it to the stack.

5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard both the parenthesis.

6. Repeat steps 2-6 until the infix expression is scanned.

7. Print the output

8. Pop and output from the stack until it is not empty.

Solution

Explanation:

Algorithm for Prefix to Infix:

• Read the Prefix expression in reverse order (from right to left)
• If the symbol is an operand, then push it onto the Stack
• If the symbol is an operator, then pop two operands from the Stack
  

  Create a string by concatenating the two operands and the operator between them.
  

  string = (operand1 + operator + operand2)
  

  And push the resultant string back to Stack

• Repeat the above steps until the end of the Prefix expression.

Solution

Following are the steps to follow to solve the Tower of Hanoi problem recursively.

Let the three pegs be A, B and C. The goal is to move n pegs from A to C.

To move n discs from peg A to peg C:

move n-1 discs from A to B. This leaves disc n alone on peg A

move disc n from A to C

move n-1 discs from B to C so they sit on disc n

The recurrence function T(n) for time complexity of the above recursive solution can be written as follows.

T(n) = 2T(n-1) + 1

Solution

Solution

For n disks, total 2n+1 -1 function calls are made.

2^6 - 1 = 63

Solution

10+3*5/(16-4)

According to precedence,

10+((3*5)/(16-4))

Alternative way to solve using stack by following stack

Algorithm

1. Scan the infix expression from left to right.

2. If the scanned character is an operand, output it.

3. Else,

…..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.

…..3.2 Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)

4. If the scanned character is an ‘(‘, push it to the stack.

5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard both the parenthesis.

6. Repeat steps 2-6 until the infix expression is scanned.

7. Print the output

8. Pop and output from the stack until it is not empty.

Solution

Solution