Making the push operation costly, select the code snippet which implements the same.(let q1 and q2 be two queues)
Posted: Wed Jul 13, 2022 7:41 pm
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)
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("e25be634-2f62-4ed5-978b-3aaec04c8aca");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("e25be634-2f62-4ed5-978b-3aaec04c8aca");
}
});
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)
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0");
}
});
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if ( adpushup.config.platform === "DESKTOP" || adpushup.config.platform === "TABLET" ) {
adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0");
}
});
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)
Check this: Data Structure Books | Programming Books
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a");
}
});
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--;
}
}
}
}
View Answer
Answer: a
Explanation: Stack follows LIFO principle, hence a new item added must be the first one to exit, but queue follows FIFO principle, so when a new item is entered into the queue, it will be at the rear end of the queue. If the queue is initially empty, then just add the new element, otherwise add the new element to the second queue and dequeue all the elements from the second queue and enqueue it to the first one, in this way, the new element added will be always in front of the queue. Since two queues are needed to realize this push operation, it is considered to be costlier.
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");
}
});
public void pop()
{
if(q1.size()>0)
{
q2.poll();
}
else if(q2.size()>0)
{
q1.poll();
}
}
b)
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");
}
});
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();
}
}
View Answer
Answer: b
Explanation: As the push operation is costly, it is evident that the required item is in the front of the queue, so just dequeue the element from the queue.
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;
}
View Answer
Answer: c
Explanation: Assuming its a push costly implementation, the top of the stack will be in the front end of the queue, note that peek() just returns the front element, while poll() removes the front element from the queue.
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();
}
View Answer
Answer: b
Explanation: If both the queues are empty, then the stack also is empty.
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;
}
View Answer
Answer: c
Explanation: Here the pop operation is costly, hence we need two queues, other than the first element, all the the elements from one queue are dequeued and enqueued to the second queue, hence only one element remains in the first queue which is the item we want, so dequeue it and return the result.
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
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)
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("e25be634-2f62-4ed5-978b-3aaec04c8aca");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("e25be634-2f62-4ed5-978b-3aaec04c8aca");
}
});
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)
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("e5da93a0-b61a-4789-96be-a57ebec165b0");
}
});
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if ( adpushup.config.platform === "DESKTOP" || adpushup.config.platform === "TABLET" ) {
adpushup.triggerAd("7cee830d-5f11-4a2b-b356-93cc453475a0");
}
});
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)
Check this: Data Structure Books | Programming Books
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a");
}
});
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--;
}
}
}
}
View Answer
Answer: a
Explanation: Stack follows LIFO principle, hence a new item added must be the first one to exit, but queue follows FIFO principle, so when a new item is entered into the queue, it will be at the rear end of the queue. If the queue is initially empty, then just add the new element, otherwise add the new element to the second queue and dequeue all the elements from the second queue and enqueue it to the first one, in this way, the new element added will be always in front of the queue. Since two queues are needed to realize this push operation, it is considered to be costlier.
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37");
}
});
public void pop()
{
if(q1.size()>0)
{
q2.poll();
}
else if(q2.size()>0)
{
q1.poll();
}
}
b)
advertisement
var adpushup = window.adpushup || {};
adpushup.que = adpushup.que || [];
adpushup.que.push(function () {
if (adpushup.config.platform === "MOBILE") {
adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");
} else if ((window.outerWidth <= 768) || (window.outerWidth == 0)) {
adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544");
}
});
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();
}
}
View Answer
Answer: b
Explanation: As the push operation is costly, it is evident that the required item is in the front of the queue, so just dequeue the element from the queue.
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;
}
View Answer
Answer: c
Explanation: Assuming its a push costly implementation, the top of the stack will be in the front end of the queue, note that peek() just returns the front element, while poll() removes the front element from the queue.
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();
}
View Answer
Answer: b
Explanation: If both the queues are empty, then the stack also is empty.
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;
}
View Answer
Answer: c
Explanation: Here the pop operation is costly, hence we need two queues, other than the first element, all the the elements from one queue are dequeued and enqueued to the second queue, hence only one element remains in the first queue which is the item we want, so dequeue it and return the result.
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