Implementing a Queue using two Stacks

We have seen how to implement Queue using a linked list and using Array as the base data structure.  The question here is that given two Stacks, say S1 and S2, and no other data structure, simulate the functionality of a Queue, hence use two stacks as the base data structure for a Queue.
i.e we should expose two functions enqueue and dequeue which will insert the element and return it in FIFO order (First In First Out).
The class for this Queue-like data structure will be something like below

class SpecialQueue{
private:
    Stack s1;
    Stack S2;
public:
    void enqueue(int data);
    int dequeue();
    bool isEmpty();
};

Actual code may have some helper functions (private functions) and Constructor and destructor,  I have not included them, just to keep the code small and to the point.
Above code is a typical example of data abstraction, because user is given an interface to access the Queue (enqueue-dequeue) and is not concerned about the underlining data structure used to store actual data of queue.
Solution:

In this case one stack is used to insert and another stack is used to remove elements. Lets rename the two Stacks as InputStack and OutputStack.

Element will always be inserted(pushed) at the top of InputStack, and removed(poped) from top of OutputStack.

When one of the stack is empty then elements from other will be poped and pushed into that stack. The order of elements in InputStack and OutputStack will be opposite. Element inserted first will be at the bottom of InputStack, but it will come at the top of OutputStack. Hence, the first element to be removed is the first one inserted (i.e FIFO).

Queue operations are all constant time operations, but in this case since elements are moved from one stack to another stack, at least one of the two operations will be O(n).

Depending on our requirements we can opt to make either enqueue faster or dequeue faster, but the other one will be slower. Below we discuss both the methods

Method-1: Enqueue takes constant time, Dequeue is O(n)

void enqueue(int x):
    1. Push x to InputStack.
int dequeue():
    1. IF (both InputStack and OutputStack are empty) THEN error.
    2. IF (OutputStack is empty)
       Pop all elements from InputStack and push them into OutputStack (one element at a time).
    3. Pop element from OutputStack and return.

Method-2: Enqueue is O(n), Dequeue takes constant time

void enqueue(int x):
    1. Pop everything from OutputStack and push it into InputStack.
    2. Push x into InputStack.
    3. Pop everything out from InputStack and push it into OutputStack.
int dequeue():
    1. IF (OutputStack is empty) THEN error.
    2. Pop element from OutputStack and return.

Method-3: Mixed Approach

Here, we keep the data in one stack only (either InputStack or OutputStack) and hence we optimize consecutive operation

void enqueue(int x):
    1. IF (OutputStack IS Non-Empty)
            Pop everything from OutputStack and push it into InputStack.
    2. Push x into InputStack.
int dequeue():
    1. IF (InputStack is Non-Empty)
            Pop everything from InputStack and push it into OutputStack.
    2. IF (OutputStack is Empty)
            Return ERROR
       ELSE
            Pop element from OutputStack and return.

In this case, if we have n-consecutive Enqueue(or n-consecutive Dequeue) operations then first one will take O(n) time and rest all will be constant time operations.

It will be worst if we are having alternate enqueue and dequeue operations.

For most cases the best option will be Method-1. Method-2 moves the elements twice between the two stacks and Method-3 may not be applicable in all situations.
Code:
Below is the code for Method-1

class SpecialQueue{
private:
    Stack inputStack;
    Stack outputStack;
public:
    void enqueue(int data);
    int dequeue();
    bool isEmpty();
};
void SpecialQueue::enqueue(int x)
{
    inputStack.push(x);
}
int SpecialQueue::dequeue()
{
    if(!outputStack.isEmpty()){
        return outputStack.pop();
    }
    if(!inputStack.isEmpty()){
        while(!inputStack.isEmpty()){
            outputStack.push(inputStack.pop());
        }
        return outputStack.pop();
    }
    // ERROR case. Queue is Empty.
    return -1;
}
bool SpecialQueue::isEmpty()
{
    return (inputStack.isEmpty() && outputStack.isEmpty());
}