Optimised solution for implementing a queue with two stacks

Question

I need help to optimise the following code in C++, which implements a queue with two stacks. Unfortunately, it's not passing some of the test cases @ the following link: https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks The (hidden) test cases yield "Terminated due to timeout 2s". How can I make my implementation faster?

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
class MyQueue {
 public:
 stack<int> stack_newest_on_top, stack_oldest_on_top;
 void push(int x) {
 /* Check if the stack_oldest_on_top is empty..
 if it is not empty, push all the elements onto
 stack_newest_on_top */
 while(true != stack_oldest_on_top.empty()) {
 stack_newest_on_top.push(stack_oldest_on_top.top());
 stack_oldest_on_top.pop();
 }
 /* When you want to push a value on to the que,
 it should be stack_newest_on_top*/
 stack_newest_on_top.push(x);
 }
 void pop() {
 /* Check if the stack_newest_on_top is empty.. */
 while(true != stack_newest_on_top.empty()) {
 /* Access the top of the newest stack */
 stack_oldest_on_top.push(stack_newest_on_top.top());
 /* After acessing the top, just pop it off */
 stack_newest_on_top.pop();
 }
 if (true != stack_oldest_on_top.empty()) {
 /* Pop the elem at the top of oldest stack. */
 stack_oldest_on_top.pop();
 }
 }
 int front() {
 int rt_value = 0;
 while(true != stack_newest_on_top.empty()) {
 stack_oldest_on_top.push(stack_newest_on_top.top());
 /* After acessing the top, just pop it off */
 stack_newest_on_top.pop();
 }
 if (true != stack_oldest_on_top.empty()) {
 /* Get the top element of the stack */
 rt_value = stack_oldest_on_top.top();
 }
 return rt_value;
 }
};
int main() {
 MyQueue q1;
 int q, type, x;
 cin >> q;
 for(int i = 0; i < q; i++) {
 cin >> type;
 if(type == 1) {
 cin >> x;
 q1.push(x);
 }
 else if(type == 2) {
 q1.pop();
 }
 else cout << q1.front() << endl;
 }
 /* Enter your code here. Read input from STDIN. Print output to STDOUT */
 return 0;
}

• 200_success: To the best of your knowledge, is the problem one of correctness, or of performance? Could you include some of your own test cases in the question?

Answer 1

Lets assume the following test case: First you push a million elements into the queue. Than you perform alternating a pop and a push. The pop will move all of the million elements of the first stack to the second one and the push will move all of them back to the first time. Every alternating push and pop call has a time complexity of O(size of queue). This is not very efficient and you get time problems really soon. And that is why you get the "Terminated due to timeout 2s" error on Hackerrank.

So copying the elements like crazy is definitely not the way to go. How can you improve it?

Here's a hint: The main error that you do is, that you assume that one of the stacks should be empty at all time. This doesn't have to be the case. Only copy if you really have to.

If you are still stuck, check out the solution:

stack_newest_on_top keeps the newest elements on top. So if you push one element into the queue, just push it onto this stack. Don't worry about the about stack_oldest_on_top.

void push(int x) {
 stack_newest_on_top.push(x);
}

If you pop/front an element, do the same thing. Just use the top element from stack_oldest_on_top. Only if stack_oldest_on_top is empty. You need to move all the elements from stack_newest_on_top to stack_oldest_on_top.

void pop() {
 if (stack_oldest_on_top.empty()) {
 while (!stack_newest_on_top.empty()) {
 stack_oldest_on_top.push(stack_newest_on_top.top());
 stack_newest_on_top.pop();
 }
 }
 stack_oldest_on_top.pop();
}

Notice, in the worst case a pop has still O(size of queue) time complexity. But it is called very rarely. In fact every element moves from the first stack only once to the second stack. This gives you an amortised time complexity of O(1).

• Venkata Pavan: Thanks a lot for your answer. Yes, it worked. And all the test cases passed @ HackerRank.

Answer 2

In addition to the comment of @user38034 I believe there are some additional things to mention: 0. The obvious namespace std; comment. This is bad practice and not needed here.

1. Why are your two stacks public? They should not be accessible from the outside.

2. You are not modifying the value of the push argument, so you should mark it const.

3. Despite this being a challenge, you should still clean your code up, this means no unneeded includes.

4. You are missing functionality. Even if you pass the tests, you should provide certain standard functionality such as: empty(), size(), clear()

5. You should avoid multiple declarations on a single line. Disk space is cheap so use it, as it increases readability by a ton.