Implement a queue using two stacks

Question

I tried to implement a queue using two stacks. I saw there are questions about this topic, but in my example, I used build-in stack from java. My question is, can someone give me some advice to make my code more efficient or better (in turn of class structure, for-loop, etc)?

This is for practising and understanding how the data structure works (Queue and stack). The main idea is to use two stacks and act as a single queue. The way I implement this problem is by assigning one stack to store odd number of elements and another one to store even number of elements. Example: if there are 3 elements, the first and the third element goes to the oddStack, the second element goes to evenStack.

import java.util.Stack;

public class twoStacksInOneQueue {

private Stack <Integer> oddStack;
private Stack <Integer> evenStack;
private int counter;// count added element
private int shift;//count internal movement from one stack to another.
/**
 Constructor
 */
public twoStacksInOneQueue()
{
    counter = 1;
    shift = 0;
    oddStack = new Stack<Integer>();
    evenStack = new Stack <Integer>();
}
/**
 add element to queue according to amount of elements.
 if there are 3 element, the 3rd element is put into odd stack.
 */
public void addToQueue(int num)
{
    if(counter % 2 == 0)
    {
        evenStack.push(num);
        System.out.println("evenStack: " +  num);
    }
    else
    {
        oddStack.push(num);
        System.out.println("oddStack: " +  num);
    }
    counter++;       
}

/**
 remove an element from queue according to amount of elements
 */
public int removeFromQueue()
{
    int temp;
    int result = 0;

    if(counter == 0)//empty queue
    {
        System.out.println("The Queue is empty!");
    }
    else if (counter % 2 == 0) //if there are even elements
    {
        while(!evenStack.empty())//loop while not empty
        {
            //move the entire stack to another to get the bottom of the stack
            temp = evenStack.pop();
            oddStack.push(temp);
            shift++;
        }
        result = oddStack.pop();//the previous bottom of the moved stack
        System.out.println("result From even: "+result);

        while (shift-1  > 0)//move the moved stack back. -1 because of the popped element above
        {
            temp = oddStack.pop();
            evenStack.push(temp);
            shift--;
        }
        counter--;
    }
    else //if there are odd elements
    {
        while(!oddStack.empty())
        {
            temp = oddStack.pop();
            evenStack.push(temp);
            shift++;
        }
        result = evenStack.pop();

        System.out.println("result from odd: "+result);
        while (shift-1 > 0)
        {
            temp = evenStack.pop();
            oddStack.push(temp);
            shift--;
        }
        counter--;
    }
    shift = 0;//reset internal moved counter.
    return result;
}

public static void main (String [] arg)
{
   twoStacksInOneQueue myQueue = new twoStacksInOneQueue();
    for (int i = 0; i< 4; i++)
    {
        myQueue.addToQueue(i+1);
    }

    myQueue.removeFromQueue();
    myQueue.removeFromQueue();
    myQueue.removeFromQueue();
    myQueue.removeFromQueue();
}

Answer 1

Improving your solution

private Stack <Integer> oddStack;
private Stack <Integer> evenStack;

I'd replace these with an array.

private Stack<Integer>[] stacks = (Stack<Integer>[])new Stack[2];

Then you don't have to keep converting from numbers to names when you use them.

private int counter;// count added element

You don't need this, as Stack has a size method.

private int shift;//count internal movement from one stack to another.

You never use this outside of a single method. Rather than creating an object field, just use a local variable.

public twoStacksInOneQueue()
{
    counter = 1;
    shift = 0;
    oddStack = new Stack<Integer>();
    evenStack = new Stack <Integer>();
}

This gets simpler.

public twoStacksInOneQueue()
{
    stacks[0] = new Stack<Integer>();
    stacks[1] = new Stack<Integer>();
}

No need for the other two here.

public void addToQueue(int num)
{
    if(counter % 2 == 0)
    {
        evenStack.push(num);
        System.out.println("evenStack: " +  num);
    }
    else
    {
        oddStack.push(num);
        System.out.println("oddStack: " +  num);
    }
    counter++;       
}

And this becomes just

public void addToQueue(int num)
{
    int index = ((stacks[0].size() + stacks[1].size()) % 2;
    stacks[index].push(num);
    System.out.println(((index == 0) ? "evenStack: " : "oddStack: ") +  num);
}

Note that this would only be one line if it weren't for printing the stack information.

    int temp;
    int result = 0;

    if(counter == 0)//empty queue
    {
        System.out.println("The Queue is empty!");
    }

I wouldn't declare temp until later, and I would return from the empty case (or throw an exception).

    if (stacks[0].empty() && stacks[1].empty())
    {
        System.out.println("The Queue is empty!");
        return 0;
    }

I'll put result back later.

        while (shift-1  > 0)//move the moved stack back. -1 because of the popped element above

You are doing an extra math operation on every iteration of the loop. But you don't have to do so. Either

        while (shift > 1)//move the moved stack back. 1 because of the popped element above

Or

        shift--; //move the moved stack back. -1 because of the popped element above
        while (shift > 0)

The latter might be more efficient on some platforms, since comparisons are often implemented as subtractions and comparisons to 0.

    else if (counter % 2 == 0) //if there are even elements
    {
        while(!evenStack.empty())//loop while not empty
        {
            //move the entire stack to another to get the bottom of the stack
            temp = evenStack.pop();
            oddStack.push(temp);
            shift++;
        }
        result = oddStack.pop();//the previous bottom of the moved stack
        System.out.println("result From even: "+result);

        while (shift-1  > 0)//move the moved stack back. -1 because of the popped element above
        {
            temp = oddStack.pop();
            evenStack.push(temp);
            shift--;
        }
        counter--;
    }
    else //if there are odd elements
    {
        while(!oddStack.empty())
        {
            temp = oddStack.pop();
            evenStack.push(temp);
            shift++;
        }
        result = evenStack.pop();

        System.out.println("result from odd: "+result);
        while (shift-1 > 0)
        {
            temp = evenStack.pop();
            oddStack.push(temp);
            shift--;
        }
        counter--;
    }
    shift = 0;//reset internal moved counter.

This seems longer than it needs to be.

    int index = ((stacks[0].size() + stacks[1].size()) % 2;
    int result = removeLast(stacks[index], stacks[1 - index]);

    System.out.println(((index == 0) ? "result From even: " : "result from odd: ") + result);

    return result;

Again, if it weren't for the output requirement, we could have returned directly.

And then just define a method for removeLast:

public static int removeLast(Stack<Integer> stack, Stack<Integer> temp)
{
    int snapshot = temp.size();

    while (!stack.empty())
    {
        temp.push(stack.pop());
    }

    int result = temp.pop();

    while (temp.size() > snapshot)
    {
        stack.push(temp.pop());
    }

    return result;
}

Rather than explicitly counting how many elements we shift, now we just reduce temp back to its original size.

Because we defined a method for this, we only have to write this logic once. We call the method with different arguments rather than duplicating the logic.

The thing is though that this method has you moving half the elements twice on every removal. We can do better. On average, we only need to move one element per removal.

An alternative solution

class StackQueue {

    private Stack<Integer> backward = new Stack<>();
    private Stack<Integer> forward = new Stack<>();

    public void enqueue(int item) {
        backward.add(item);
    }

    public int dequeue() {
        if (forward.empty()) {
            if (backward.empty()) {
                // throwing an exception would likely be better
                return 0;
            }

            do {
                forward.push(backward.pop());
            } while (!backward.empty());
        }

        return forward.pop();
    }

}

This gives constant time enqueue operations and on average gives constant time dequeue operations. When I say "on average", I mean that it moves each element from backward to forward once per removal. However, on a particular operation, it moves either 0 or all of them.