1 Crore+ students have signed up on EduRev. Have you? 
Which of the following is true about linked list implementation of stack?
To keep the Last In First Out order, a stack can be implemented using linked list in two ways:
a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from beginning.
b) In push operation, if new nodes are inserted at the end of linked list, then in pop operation, nodes must be removed from end.
Consider the following pseudocode that uses a stack
declare a stack of characters
while ( there are more characters in the word to read )
{
read a character
push the character on the stack
}
while ( the stack is not empty )
{
pop a character off the stack
write the character to the screen
}
What is output for input “geeksquiz”?
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())
Following is an incorrect pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced:
declare a character stack
while ( more input is available)
{
read a character
if ( the character is a '(' )
push it on the stack
else if ( the character is a ')' and the stack is not empty )
pop a character off the stack
else
print "unbalanced" and exit
}
print "balanced"
Which of these unbalanced sequences does the above code think is balanced?
At the end of while loop, we must check whether the stack is empty or not. For input ((()), the stack doesn’t remain empty after the loop.
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:
The algorithm for evaluating any postfix expression is fairly straightforward:
1. While there are input tokens left
o Read the next token from input.
o If the token is a value
+ Push it onto the stack.
o Otherwise, the token is an operator
(operator here includes both operators, and functions).
* It is known a priori that the operator takes n arguments.
* If there are fewer than n values on the stack
(Error) The user has not input sufficient values in the expression.
* Else, Pop the top n values from the stack.
* Evaluate the operator, with the values as arguments.
* Push the returned results, if any, back onto the stack.
2. If there is only one value in the stack
o That value is the result of the calculation.
3. If there are more values in the stack
o (Error) The user input has too many values.
Let us run the above algorithm for the given expression.
First three tokens are values, so they are simply pushed. After pushing 8, 2 and 3, the stack is as follows
8, 2, 3
When ^ is read, top two are popped and power(2^3) is calculated
8, 8
When / is read, top two are popped and division(8/8) is performed
1
Next two tokens are values, so they are simply pushed. After pushing 2 and 3, the stack is as follows
1, 2, 3
When * comes, top two are popped and multiplication is performed.
1, 6
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< top 2) 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
If we are to use space efficiently then size of the any stack can be more than MAXSIZE/2.
Both stacks will grow from both ends and if any of the stack top reaches near to the other top then stacks are full. So the condition will be top1 = top2 1 (given that top1 < top2)
To evaluate an expression without any embedded function calls:
Any expression can be converted into Postfix or Prefix form.
Prefix and postfix evaluation can be done using a single stack.
For example : Expression ’10 2 8 * + 3 ‘ is given.
PUSH 10 in the stack.
PUSH 2 in the stack.
PUSH 8 in the stack.
When operator ‘*’ occurs, POP 2 and 8 from the stack.
PUSH 2 * 8 = 16 in the stack.
When operator ‘+’ occurs, POP 16 and 10 from the stack.
PUSH 10 * 16 = 26 in the stack.
PUSH 3 in the stack.
When operator ‘‘ occurs, POP 26 and 3 from the stack.
PUSH 26 – 3 = 23 in the stack.
So, 23 is the answer obtained using single stack.
A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i.
If a stack S contains the integers 2, 3, 2, 1, 2 in order from bottom to top, what is f(S)?
f(S) = 0, max(f(S), 0) = 0, i = 2
f(S)new = max(f(S), 0) + i = 0 + 2 = 2
f(S) = 2, max(f(S), 0) = 2, i = 3
f(S)new = max(f(S), 0) + i = 2 – 3 = 1
f(S) = 1, max(f(S), 0) = 0, i = 2
f(S)new = max(f(S), 0) + i = 0 + 2 = 2
f(S) = 2, max(f(S), 0) = 2, i = 1
f(S)new = max(f(S), 0) + i = 2 – 1 = 1
f(S) = 1, max(f(S), 0) = 1, i = 2
f(S)new = max(f(S), 0) + i = 1 + 2 = 3
Thus, option (C) is correct.
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 + * +
The function of the program is:
1) If the current character is a digit it pushes into stack
2) Else if the current character is operator, it pops two elements and then performs the operation.
Finally it pushes the resultant element into stack.
Initially stack s is empty. 5 2 * 3 3 2 + * +
1) 5 > It pushes into s
2) 2 > It pushes into s
3) * > It pops two elements n = 2, m=5 n*m = 10 It pushes 10 into s
4) 3 > It pushes into s
5) 3 > It pushes into s
6) 2 > It pushes into s
7) + > n=2, m=3 n+m=5 It pushes 5 into s
8) * > n=5, m=3 n*m=15 It pushes 15 into s
9) + > n=15, m=10 n+m = 25 It pushes 25 into s.
A priority queue Q is used to implement a stack S that stores characters. PUSH(C) is implemented as INSERT(Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in
We are implementing a STACK using Priority Queue. Note that Stack implementation is always last in first out (LIFO) order.
As given “POP is implemented as DELETEMIN(Q)” that means Stack returns minimum element always.
So, we need to implement PUSH(C) using INSERT(Q, C, K) where K is key chosen from strictlydecreasing order(only this order will ensure stack will return minimum element when we POP an element). That will satify Last In First Out (LIFO) property of stack.
That is answer, option (D) is true.
Option (A) nonincreasing order can not be true because two same (identical) numbers can not have same priority as priority should be distinguishable for each number.
The seven elements A, B, C, D, E, F and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times and each element is inserted into a queue.Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. The popped item is ________.
In fig:1 elements are inserted into a stack then in fig:2 top 5 elements are popped and these 5 elements are inserted into a queue which is shown in fig:3, now first two elements are deleted from queue and pushed into stack one by one which is shown in fig:5.
At top of the stack element B is presented.
So, option (B) is correct.
If the sequence of operations – push (1), push (2), pop, push (1), push (2), pop, pop, pop, push (2), pop are performed on a stack, the sequence of popped out values
The pop sequence can be seen from the following table:
Consider the following sequence of operations on an empty stack.
Push(54);push(52);pop();push(55);push(62);s=pop();
Consider the following sequence of operations on an empty queue.
enqueue(21);enqueue(24);dequeue();enqueue(28);enqueue(32);q=dequeue();
The value of s+q is ___________.
Let’s construct an empty stack and do the operations. Stack follows LIFO order.
1.Push(54) // (54)
2.Push(52) // (54,52)
3.Pop() // (54)
4.Push(55) //(54,55)
5.Push(62) //(54,55,62)
6.s=pop() // (54,55)
s=62;
Let’s construct an empty queue and do the operations. Queue follows FIFO order.
1.Enqueue(21) // [21]
2.Enqueue(24) // [21,24]
3.Dequeue() // [24]
4.Enqueue(28) // [24,28]
5.Enqueue(32) // [24,28,32]
6.q=Dequeue() // [28,32]
q=24;
s+q=62+24
So, s+q=86 .
Convert the following infix expression into its equivalent post fix expression (A + B^ D) / (E – F) + G
(A + B^ D) / (E – F) + G
= (A + B^ D)(E – F)/ + G
= (A + B^ D)(E – F)/G+
= A + BD^(E – F)/G+
= ABD^+EF/G+
So, option (A) is correct.
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
When five items: A, B, C, D, and E are pushed in a stack: Order of stack becomes: A, B, C, D, and E (A at the bottom and E at the top.) stack is popped four items and each element is inserted in a queue: Order of queue: B, C, D, E (B at rear and E at the front) Order of stack after pop operations = A. Two elements deleted from the queue and pushed back on the stack: New order of stack = A, E, D(A at the bottom, D at the top) As D is on the top so when pop operation occurs D will be popped out. So, correct option is (D).
Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. An entry popped out of the stack B can be only be printed. In this arrangement, which of the following permutations of a, b, c are not possible?
Option (A):
Pop a from stack A
Push a to stack B
Print b
Print a from stack B
Print c from stack A
Order = b a c
Option (B):
Pop a from stack A
Push a to stack B
Print b from stack A
Print c from stack A
Print a from stack A
Order = b c a
Option (C):
Pop a from stack A
Push a to stack B
Pop b from stack A
Push b to stack B
Print c from stack A
Now, printing a will not be possible.
So, option (C) is incorrect.
71 docs29 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
71 docs29 tests









