Optimised solution for implementing a queue with two stacks

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
#include
#include
#include
#include
#include
#include
using namespace std;

class MyQueue {
public:
stack 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()) {
/* G

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).

StackExchange Code Review Q#157619, answer score: 2