## Stacks

 Question 1
The following postfix expression with single digit operands is evaluated using a stack:
`8 2 3 ^ / 2 3 * + 5 1 * -`
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
 A 6, 1 B 5, 7 C 3, 2 D 1, 5
Data-Structures       Stacks       Gate-2007
Question 1 Explanation:
8 2 3 ^ / 2 3 * + 5 1 * - After the * is evaluated at the time elements in the stack is 1, 6.
 Question 2
Consider the following C program:
```   #include
#define EOF -1
void push (int); /* push the argument on the stack */
int pop  (void); /* pop the top of the stack */
void flagError ();
int main ()
{         int c, m, n, r;
while ((c = getchar ()) != EOF)
{ if  (isdigit (c) )
push (c);
else if ((c == '+') || (c == '*'))
{          m = pop ();
n = pop ();
r = (c == '+') ? n + m : n*m;
push (r);
}
else if (c != ' ')
flagError ();
}
printf("% c", pop ());
}
```
What is the output of the program for the following input ? 5 2 * 3 3 2 + * +
 A 15 B 25 C 30 D 150
Data-Structures       Stacks       Gate 2007-IT
Question 2 Explanation:
push 5
push 2
pop 2
pop 5
5 * 2 = 10
push 10
push 3
push 3
push 2
pop 2
pop 3
3 + 2 = 5
push 5
pop 5
pop 3
3 * 5 = 15
push 15
pop 15
pop 10
10 + 15 = 25
push 25
Finally, pop 25 and print it.
 Question 3
A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl < top2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is
 A (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1) B top1 + top2 = MAXSIZE C (top1 = MAXSIZE/2) or (top2 = MAXSIZE) D top1 = top2 – 1
Data-Structures       Stacks       Gate-2004
Question 3 Explanation:
Since the stacks are growing from opposite ends, so initially top1=1 and top2=Max_size. Now to make the efficient use of space we should allow one stack to use the maximum possible space as long as other stack doesn't need it. So any of the stack can grow towards each other until there is space available in the array. Hence, the condition must be top1=top2 - 1.
 Question 4
The best data structure to check whether an arithmetic expression has balanced parentheses is a
 A queue B stack C tree D list
Data-Structures       Stacks       Gate-2004
Question 4 Explanation:
Stack is the best data structure to validate the arithmetic expression.
While evaluating when left parentheses occur then it push in to the stack, when right parentheses occur pop from the stack.
While at the end there is empty in the stack.
 Question 5
Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, x , +, -. The postfix expression corresponding to the infix expression a + b×c-d^e^f is
 A abc×+def^^- B abc×+de^f^- C ab+c×d-e^f^ D -+a×bc^^def
Data-Structures       Stacks       Gate-2004
Question 5 Explanation:
a+b×c-d^e^f Note: When low precedence operator enters into stack then pop.
 Question 6
Let S be a stack of size n ≥1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m ≥1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is
 A n(X + Y) B 3Y + 2X C n(X + Y) - X D Y + 2X
Data-Structures       Stacks       Gate-2003
Question 6 Explanation:
Life time of last element present in the stack = Y
(After push into stack then immediately popped)
Life time of (n-1) element = Y + X + Y + X + Y = 2X + 3Y
Life time of (n-2) element = (n-1) + 2X + 2Y = 2X + 3Y + 2X + 2Y = 4X + 5Y
Life time of 1's element = 2(n-1)X + (2n-1)Y
Life time of all elements is ⇒
2X(1+2+3+...+n-1)+Y(1+3+5+...+(2n-1))
⇒ 2X(n(n-1) /2) +Y((n/2)(1+2n-1))
⇒ n(n(X+Y)-X))
Avg. of n numbers = n(n(X+Y)-X)/n = n(X+Y)-X
 Question 7
To evaluate an expression without any embedded function calls
 A One stack is enough B Two stacks are needed C As many stacks as the height of the expression tree are needed D A Turning machine is needed in the general case
Data-Structures       Stacks       Gate-2002
Question 7 Explanation:
To evaluate an expression or converting prefix to postfix, postfix to prefix only one stack is enough.
 Question 8
Which of the following is essential for converting an infix expression to the postfix form efficiently?
 A An operator stack B An operand stack C An operand stack and an operator stack D A parse tree
Data-Structures       Stacks       Gate-1997
Question 8 Explanation:
An operator stack ⇒ Infix to (Postfix or Prefix)
An operand stack ⇒ Postfix to Prefix
Operator & operand stack ⇒ We don't use two stacks
Parse tree ⇒ No use
 Question 9
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?
 A 3, 4, 5, 1, 2 B 3, 4, 5, 2, 1 C 1, 5, 2, 3, 4 D 5, 4, 3, 1, 2
Data-Structures       Stacks       Gate-1994
Question 9 Explanation:
Push 1 Push 2 Push 3 Pop 3 Push 4 Pop 4 Push 5 Pop 5 Pop 2 Pop 1.
→ Remaining options are not possible.
 Question 10
 A 20, 10, 20, 10, 20 B 20, 20, 10, 10, 20 C 10, 20, 20, 10, 20 D 20, 20, 10, 20, 10
Algorithms       Stacks       Gate-1991
Question 10 Explanation:
PUSH(10), PUSH(20), POP = 20 (i)
→ PUSH(10), PUSH(10), PUSH(20), POP = 20 (ii)
→ PUSH(10), PUSH(10), POP = 10 (iii)
→ PUSH(10), POP = 10 (iv)
→ PUSH(20)
→ PUSH(20), POP = 20 (v)
20, 20, 10, 10, 20
There are 10 questions to complete.