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:
6, 1 | |
5, 7 | |
3, 2 | |
1, 5 |
Question 1 Explanation:
8 2 3 ^ / 2 3 * + 5 1 * -
After the * is evaluated at the time elements in the stack is 1, 6.
After the * is evaluated at the time elements in the stack is 1, 6.
Question 2 |
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
(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
| |
top1 + top2 = MAXSIZE
| |
(top1 = MAXSIZE/2) or (top2 = MAXSIZE)
| |
top1 = top2 – 1 |
Question 2 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.
There are 2 questions to complete.