Amazon Question: Implement queue using stacks

Problem: Given a stack data structure that supports standard operations like push() and pop(), implement a queue using given stack data structure.

Solution: Use two stacks.

Implementation:

class Queue
{
public:
Queue(){}
void insert(int i);
int remove();
bool isEmpty();
~Queue(){}
private:
std::stack<int> st1, st2;
};

void Queue::insert(int i)
{
st1.push(i);
}

int Queue::remove()
{
if(isEmpty())
return -1; //Error

if(st2.empty())
{
while(!st1.empty())
{
st2.push(st1.top());
st1.pop();
}
}

int retval = st2.top();
st2.pop();
return retval;
}

bool Queue::isEmpty()
{
return st1.empty() && st2.empty();
}

Complexity: insert - O(1), remove - O(n)