Queues-and-Stacks
Question 1 |
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below.
The maximum possible number of iterations of the while loop in the algorithm is _________.
256 | |
257 | |
258 | |
259 |
Try to solve it for 3 numbers [1. 2, 3].
Step 1: Initially Queue contains 3 elements so after 5 while loop iterations queue contains 3, 2 and stack contains 1.
Step 2: Now after 3 more while loop iterations, Queue contains 3 and stack contains 1, 2 (TOS = 2).
Step 3: After 1 more while loop iteration, push 3 onto the stack so queue is empty and stack contains 1, 2, 3 {top = 3}.
So, total number of iterations will be 5 + 3 + 1 = 9
i.e., for 3 it is 9 iterations (3*3)
for 4 it is 16 iterations (4*4)
Given: 16 numbers, so 16 * 16 = 256
Question 2 |
What is the minimum number of stacks of size n required to implement a queue of size n?
One | |
Two | |
Three | |
Four |
Question 3 |
Consider the following statements:
- (i) First-in-first out types of computations are efficiently supported by STACKS.
(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
(iv) Last-in-first-out type of computations are efficiently supported by QUEUES.
Which of the following is correct?
(ii) and (iii) are true | |
(i) and (ii) are true | |
(iii) and (iv) are true | |
(ii) and (iv) are true |
(iv) LIFO computation efficiently supported by stacks.
Then given (i) and (iv) are false.
Answer:- A
Question 4 |
A queue Q containing n items and an empty stack S are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the top of the stack, and the order of all other items is preserved. Show how this can be done in O(n) time using only a constant amount of additional storage. Note that the only operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.
Theory Explanation. |
Question 5 |
A stack is used to pass parameters to procedures in a procedure call.
(a) If a procedure P has two parameters as described in procedure definition:
procedure P (var x :integer; y: integer);
and if P is called by ; P(a,b)
State precisely in a sentence what is pushed on stack for parameters a and b.
(b) In the generated code for the body of procedure P, how will the addressing of formal parameters x and y differ?
Theory Explanation. |
Question 6 |
An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert(Q, x) {
push (S1, x);
}
void delete(Q){
if(stack-empty(S2)) then
if(stack-empty(S1)) then {
print(“Q is empty”);
return;
}
else while (!(stack-empty(S1))){
x=pop(S1);
push(S2,x);
}
x=pop(S2);
}
Let n insert and m(<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
n+m ≤ x < 2n and 2m ≤ y ≤ n+m | |
n+m ≤ x< 2n and 2m ≤y ≤ 2n | |
2m ≤ x< 2n and 2m ≤ y ≤ n+m | |
2m ≤ x < 2n and 2m ≤ y ≤ 2n |
Best case:
First push m elements in S1 then pop m elements from S1 and push them in S2 and then pop all m elements from S2. Now push remaining (n-m) elements to S1.
So total push operation
= m + m + (n-m)
= n+m
Worst Case:
First push all n elements in S1. Then pop n elements from S1 and push them into S2. Now pop m elements from S2.
So total push operation
= n+n
= 2n
Now lets consider for pop operation, i.e., y.
For best case:
First push m elements in S1, then pop m elements and push them in S2. Now pop that m elements from S2. Now push remaining (n-m) elements in S1.
So total pop operation
= m+m
= 2m
For worst case:
First push n elements in S1, then pop them from S1 and push them into S2. Now pop m elements fro m S2.
So total pop operation
= n+m
Therefore, option A is correct answer.
Question 7 |
A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented 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
non-increasing order | |
non-decreasing order | |
strictly increasing order | |
strictly decreasing order |
Question 8 |
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)?
6 | |
4 | |
3 | |
2 |
f(Ø)=0 and f(push(S,i) = max(f(S),0) + i;
Initially stack is empty and for empty stack 0 is given.
f(push(0,2)) = max(f(Ø),0) + 2 = max(Ø,0) + 2 = 2
f(push(2,-3)) = max(2,0) + (-3) = 2 - 3 = -1
f(push(-1,2)) = max(-1,0) + 2 = 0 + 2 = 2
f(push(2,-1)) = max(2,0)+ (-1) = 2 - 1 = 1
f(push(1,2)) = max(1,0) + 2 = 1 + 2 = 3
So, 3 will be the answer.
∴ Option C is correct.
Question 9 |
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 ________
86 |
push(54) ⇒ 54
push(52)=> 54, 52(top)
pop() ⇒ 54 (top)
push(55)==> 54, 55(top)
push(62) ⇒ 54,55,62(top)
s=pop() ⇒ 62 will store into the variable s then s=62
enqueue(21) ⇒ (front) 21(rear)
enqueue(24) ⇒ (Front)21, 24(rear)
dequeue()==> (front) 24(rear)
enqueue(28) ===> (front) 24,28 (rear)
enqueue(32)====>(front) 24,28,32 (rear)
q=dequeue() ⇒ value 24 will store into the variable “q”
q=24
S+q =62+24 =86
Question 10 |
I: push the elements of a from a0 to a5 in that order into S.
II: enqueue the elements of a from a0 to a5 in that order into Q.
III: pop an element from S.
IV: dequeue an element from Q.
V: pop an element from S.
VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same element into S.
VIII: Repeat operation
VII three times. IX: pop an element from S. X: pop an element from S.
The top element of S after executing the above operations is _____?
8 |
I: push the elements from a0 to a5 in that order into S.
II: enqueue the elements of a from a0 to a5 in that order into Q.

III: pop an element from S.
IV: dequeue an element from Q.
V: pop an element from S.
VI: dequeue an element from Q.

VII: dequeue an element from Q and push the same element into S.
Element “7” is deleted and inserted into stack “S”

VIII: Repeat operation VII three times.
After performing the VIII operation , the elements of stack are as shown below
IX: pop an element from S.

X: pop an element from S

The top element of S after executing the above operations is 8.
Question 11 |
A | |
B | |
C | |
D |
Question 12 |
Queue | |
Stack | |
Tree | |
List |
→ While evaluating when left parentheses occur then it pushes into the stack when right parentheses occur pop from the stack. While at the end there is empty in the stack.
Question 13 |
b a c | |
b c a | |
c a b | |
a b c |
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.
Question 14 |
A | |
B | |
C | |
D |

Question 15 |
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 |
Rule (1): If the element is a number, Push it into stack.
Rule (2): If the element is an operator, Pop operands from the stack. Evaluate the operator operation and Push the result back into the stack.

Question 16 |
q[0] | |
q[1] | |
q[9] | |
q[10] |
The front and rear pointers are initialized to point at q[2] which means third element.
First element will add at q[3] , second element will add at q[4] and so on eight element will add at q[10].
Q[10] is the end of the queue which is connected to q[0]
So ninth element can be added at q[0] pointer
Question 17 |
A | |
B | |
C | |
D |
Question 18 |
Values of local variables | |
Return address | |
Heap area | |
Information needed to access non local variables |
Variables allocated on the stack are stored directly to the memory and access to this memory is very fast, and it's allocation is dealt with when the program is compiled
Variables allocated on the heap have their memory allocated at run time and accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory . Element of the heap have no dependencies with each other and can always be accessed randomly at any time
Question 19 |
Two stacks are required | |
One stack is needed | |
Three stacks are required | |
More than three stacks are required |
Converting infix expression into post/prefix expression
Evaluating post/pre-fix expression
Parenthesis matching
With one stack also we can easily evaluate the expression.
Question 20 |
Circular queue | |
Priority queue | |
Stack | |
Dequeue |
● What makes a deque different is the unrestrictive nature of adding and removing items.New items can be added at either the front or the rear.
● Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.
Question 21 |
abc x+def^^- | |
abc xde^f^- | |
ab +c xd -e^f ^ | |
-+ a x bc ^^def |
⟶ left to right
Step 1: abc+

Question 22 |
10,8,7,3,2,1,5 | |
10,8,7,2,3,1,5 | |
10,8,7,1,2,3,5 | |
10,8,7,5,3,2,1 |
The level order traversal in this max heap final is:10, 8, 7, 3, 2, 1, 5.
Question 23 |
Array | |
Tree | |
Stack | |
Queue |
→ Stack to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes.
→ The functions follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive function calls.
→ This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.
Question 24 |
1 | |
2 | |
3 | |
4 |
push(s,x)
1) Enqueue x to q1 (assuming size of q1 is unlimited). pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
→ Implementing queue by using two stack:
(1) When calling the enqueue method, simply push the elements into the stack 1.
(2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.
