Data Structure: Unit II (a): Stacks

Two marks Questions with Answers

Stacks | ADT Data Structure

In computer system the memory model consists of stack memory stores types of variables that have a fixed lifetime based on how C programs run.

Two Marks Questions with Answers

Q.1 Give an example that shows how a stack is used by a computer system. 

Ans. : In computer system the memory model consists of stack memory stores types of variables that have a fixed lifetime based on how C programs run. It is a section of RAM that grows and shrinks as the program runs. When you call a function, its parameters and any variables you have defined in that function (which are not static) are stored on the stack.

Q.2 What do you understand by polish notation? Explain.

Ans. This is also called as prefix notation. In this type of notation the operator followed by two operands. For example if (a+b)*c is a given expression then its polish notation will be *+ abc.

Q.3 What is a top pointer of a stack ?

Ans. The top denotes the only one end of the stack from which the element can be inserted or deleted. When we push the element onto the stack, the top is incremented. When we pop the element from the stack the top is decremented.

Q.4 Write the postfix notation for following expression. (A+B)*C-(D-E)^F

Ans. Following steps can be followed for computing the postfix expression -

Step 1: (AB+)*C-(D-E)^F

Step 2: (AB+C*)-(D-E)^F

Step 3: (AB+C*)-(DE-)^F

Step 4: (AB+C*)-(DE-F^)

Step 5: AB+C*DE-F^-

Q.5 Write any two applications of stack.

Ans. : The stack can be used for -

1. Conversion of expression from one form to another. Various forms of expression are infix, prefix and postfix.

2. Evaluation of postfix expression.

3. Evaluation of recursive functions.

4. Reversing the string.

5. For checking the well formedness of parenthesis.

Q.6 List the characteristics of stacks.

Ans;

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.

Q.7 Write the role of stack in function call.

Ans. : 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.

Q.8 What is Last-In-First-Out strategy? Which data structure follows this strategy?

 Ans. : 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 stack data structure makes use of Last In First Out(LIFO) data structure.

Q.9 Write the steps to reverse the contents of the list with the help of stack data structure.

 Ans

Step 1: Read each element from the list and push it onto the stack.

Step 2: Pop the element from the stack and store the popped element in a separate array.

Step 3: Read the array completely from left to write. This will be the reversed list of the elements.

Q.10 Which data structure is used in handling the recursive function ? Ans. : The stack is used to handle the recursive function call.

Q.11 Given the prefix for an expression write its postfix. -*- +abc/ef-g/hi

Ans. :

Q.12 Give the infix for an expression, write its prefix a* b/c + d?

 Ans. : The prefix expression is /* ab + cd.

Q.13 Convert the following infix expression to postfix expression using Stack.

Ans. :

The required postfix expression is abc*def++g/+.

Q.14 State the rules to be followed during infix to postfix conversion.

Ans. :

Algorithm                                            

Read an expression from left to right each character one by one

1. If an operand is encountered then add it to postfix array.

2. If '(' is read, then simply push it onto the stack. Because the (has highest priority when read as an input.

3. If ')' is reads, then pop all the operands until (is read. Discard (. Store the popped characters in the postfix array.

4. If operator is read then

i) If instack operator has greatest precedence (or equal to) over the incoming operator then pop the operator and add it to postfix expression. Repeat this step until we get the instack operator of higher priority than the current incoming operator. Finally push the incoming operator onto the stack.

ii)  Else push the operator.

5. The postfix expression in in array.

The priorities of different operators when they are in stack will be called instack operators and the priorities of different operator when they are read from input will be called as incoming priorities.

Data Structure: Unit II (a): Stacks : Tag: : Stacks | ADT Data Structure - Two marks Questions with Answers