1. To implement a stack using queue(with only enqueue and dequeue operations), how many queues will you need?
a) 1
b) 2
c) 3
d) 4
Answer: b
Explanation:
To implement a queue with two stacks, one operation (either push or pop) becomes costly. Pop typically requires transferring elements between the two stacks, making it O(n) in the worst case.
2. Making the push operation costly, select the code snippet which implements the same.(let q1 and q2 be two queues)
a)
public void push(int x)
{
if(empty())
{
q1.offer(x);
}
else{
if(q1.size()>0)
{
q2.offer(x);
int size = q1.size();
while(size>0)
{
q2.offer(q1.poll());
size--;
}
}
else if(q2.size()>0)
{
q1.offer(x);
int size = q2.size();
while(size>0)
{
q1.offer(q2.poll());
size--;
}
}
}
}b)
public void push(int x)
{
if(empty())
{
q1.offer(x);
}
else
{
if(q1.size()>0)
{
q1.offer(x);
int size = q1.size();
while(size>0)
{
q2.offer(q1.poll());
size--;
}
}
else if(q2.size()>0)
{
q2.offer(x);
int size = q2.size();
while(size>0)
{
q1.offer(q2.poll());
size--;
}
}
}
}c)
public void push(int x)
{
if(empty())
{
q1.offer(x);
}
else
{
if(q1.size()>0)
{
q2.offer(x);
int size = q1.size();
while(size>0)
{
q1.offer(q2.poll());
size--;
}
}
else if(q2.size()>0)
{
q1.offer(x);
int size = q2.size();
while(size>0)
{
q2.offer(q1.poll());
size--;
}
}
}
}d)
public void push(int x)
{
if(empty())
{
q1.offer(x);
}
else
{
if(q1.size()>0)
{
q2.offer(x);
int size = q1.size();
while(size>0)
{
q2.offer(q2.poll());
size--;
}
}
else if(q2.size()>0)
{
q1.offer(x);
int size = q2.size();
while(size>0)
{
q2.offer(q1.poll());
size--;
}
}
}
}Answer: a
Explanation:
A stack follows the LIFO (Last In First Out) principle, meaning the most recently added item is the first one to exit. A queue follows FIFO (First In First Out), meaning elements are processed in the order they are added. To simulate a queue using two stacks, the new element must be added at the rear. This requires transferring all elements from one stack to the other to maintain the FIFO order, making the “push” operation costlier.
3. Making the push operation costly, select the code snippet which implements the pop operation.
a)
public void pop()
{
if(q1.size()>0)
{
q2.poll();
}
else if(q2.size()>0)
{
q1.poll();
}
}b)
public void pop()
{
if(q1.size()>0)
{
q1.poll();
}
else if(q2.size()>0)
{
q2.poll();
}
}c)
public void pop()
{
q1.poll();
q2.poll();
}d)
public void pop()
{
if(q2.size()>0)
{
q1.poll();
}
else
{
q2.poll();
}
}Answer: b
Explanation:
Since the push operation is costly, the item added to the queue will be in the front. To retrieve it, simply perform the dequeue operation, which removes the front element efficiently.
4. Select the code snippet which returns the top of the stack.
a)
public int top()
{
if(q1.size()>0)
{
return q1.poll();
}
else if(q2.size()>0)
{
return q2.poll();
}
return 0;
}b)
public int top()
{
if(q1.size()==0)
{
return q1.peek();
}
else if(q2.size()==0)
{
return q2.peek();
}
return 0;
}c)
public int top()
{
if(q1.size()>0)
{
return q1.peek();
}
else if(q2.size()>0)
{
return q2.peek();
}
return 0;
}d)
public int top()
{
if(q1.size()>0)
{
return q2.peek();
}
else if(q2.size()>0)
{
return q1.peek();
}
return 0;
}Answer: c
Explanation:
In a push-costly queue implementation, the top of the stack will be at the front of the queue. The peek() operation simply returns the front element without removing it, whereas poll() removes the front element from the queue, which involves dequeuing.
5. Select the code snippet which return true if the stack is empty, false otherwise.
a)
public boolean empty()
{
return q2.isEmpty();
}b)
public boolean empty()
{
return q1.isEmpty() || q2.isEmpty();
}c)
public boolean empty()
{
return q1.isEmpty();
}d)
public boolean empty()
{
return q1.isEmpty() & q2.isEmpty();
}Answer: b
Explanation:
If both queues are empty in a two-queue stack implementation, it means that there are no elements left to pop or push, so the stack is empty.
6. Making the pop operation costly, select the code snippet which implements the same.
a)
public int pop()
{
int res=-999,count=0;
if(q1.size()>0)
{
count = q1.size();
while(count>0)
q2.offer(q1.poll());
res = q1.poll();
}
if(q2.size()>0)
{
count = q2.size();
while(count>0)
q1.offer(q2.poll());
res = q2.poll();
}
return res;
}b)
public int pop()
{
int res=-999,count=0;
if(q1.size()>0)
{
count = q1.size();
while(count>1)
q2.offer(q1.poll());
res = q2.poll();
}
if(q2.size()>0)
{
count = q2.size();
while(count>1)
q1.offer(q2.poll());
res = q1.poll();
}
return res;
}c)
public int pop()
{
int res=-999,count=0;
if(q1.size()>0)
{
count = q1.size();
while(count>1)
q2.offer(q1.poll());
res = q1.poll();
}
if(q2.size()>0)
{
count = q2.size();
while(count>1)
q1.offer(q2.poll());
res = q2.poll();
}
return res;
}d)
public int pop()
{
int res=-999,count=0;
if(q1.size()>0)
{
count = q2.size();
while(count>1)
q2.offer(q1.poll());
res = q1.poll();
}
if(q2.size()>0)
{
count = q1.size();
while(count>1)
q1.offer(q2.poll());
res = q2.poll();
}
return res;
}Answer: c
Explanation:
In a two-queue stack implementation with a costly pop operation, all elements except the first one are dequeued from the first queue and enqueued into the second queue. This leaves the desired element in the first queue, which is then dequeued and returned as the result.
7. What is the functionality of the following piece of code?
public void fun(int x)
{
q1.offer(x);
}a) Perform push() with push as the costlier operation
b) Perform push() with pop as the costlier operation
c) Perform pop() with push as the costlier operation
d) Perform pop() with pop as the costlier operation
Answer: b
Explanation:
The offer() operation suggests a push operation, but since it’s implemented with only one queue, the pop operation becomes costlier. In a single queue, you must dequeue and enqueue elements to maintain the stack-like behavior, making the pop operation more expensive.