Class that implements a queue using two stacks

Question

I am looking for a review of my code that implements a MyQueue class which implements a queue using two stacks.

public class MyQueue<T> {
  Stack<T> stackNewest, stackOldest;

  public MyQueue() {
    stackNewest = new Stack<T>();
    stackOldest = new Stack<T>();
  }

  public int size() {
    return stackNewest.size() + stackOldest.size();
  }

  public void add(T value) {
    // push ont stackNewest, which always has the newest elements on top
    stackNewest.push(value);
  }

  // move elements from stackNewest into stackOldest. this is usually done so that operations can be done on stackOldest
  private void shiftStacks() {
    if (stackOldest.isEmpty()) {
      while (!stackNewest.isEmpty()) {
        stackOldest.push(stackNewest.pop());
      }
    }
  }

  public T peek() {
    shiftStacks(); // ensure stackOldest has the current elements
    return stackOldest.peek(); // retrieve the oldest item
  }

  public T remove() {
    shiftStacks(); // ensure stackOldest has the current elements
    return stackOldest.pop(); // pop the oldest item
  }
}

Answer 1

Unfortunately your code does not implement a queue. It is relatively easy to produce circumstances which break the logic. Consider the following, for example:

MyQueue<String> q = new MyQueue<>();

q.add("a");
q.add("b");
q.remove(); // should be "a", and is "a".
q.add("c");
q.remove(); // should be "b", but is "c".
q.remove(); // should be "c", but is "b".

Using two stacks to implement a queue is not a logical data structure as far as I am concerned. There are many better ways.

Answer 2

private void shiftStacks() {
if (stackOldest.isEmpty()) {
  while (!stackNewest.isEmpty()) {
    stackOldest.push(stackNewest.pop());
  }
}
}

This portion will be expensive when you have interleaved add and remove operations. Each remove will execute this block unnecessarily. Would be best to do so once and keep popping from the secondary stack until it is empty. It still helps you maintain your FIFO order.

Answer 3

Set up the stage

Let's make it easier by using something concrete, say, poker cards.

Suppose you have four cards: A, 4, 6, 9, and you have two stacks.

As the name suggests, for the stacks, you can only put on a new card to the top of the stack, or take the top card off the stack.

To make it simple, let's keep the order (A, 4, 6, 9).

What we want is to make the box a queue. That means when you take out cards from the box, they should keep the order. In other words, if 4 is latest card taken out, the next card (if any) would be 6.

Before we play, picture this box with two stacks inside (L and R).

For the stacks L and R, ) marks the top, where you put a card in or take a card out.

~~~~~~~~~~~~~~~~~~~~
|                  |
| [  L  )  [  R  ) |
|__________________|

Let the play begin

Ok let's play with the cards.

1. put A in the box
2. put 4 in the box
3. take out a card from the box; it should be A
4. put 6 in the box
5. put 9 in the box
6. take out a card from the box; it should be 4
7. show me the next card in the box; it should be 6
8. take out a card; it should be 6
9. take out a card; it should be 9

Behind the scenes

One can make it work like this: (for the above steps)

1.  [A)      [ )
2.  [A 4)    [ )
3a. [A)      [4)
3b. [ )      [4 A)
3c. [ )      [4)     ---> A
3d. [4)      [ )
4.  [4 6)    [ )
4.  [4 6 9)  [ )
(... you got the idea ...)

Back to the code

So... what is the different between this and your code?

Answer 4

OK, I am quite sure that the OP's implementation is correct. @rolfl was marked as the correct answer is not right.

MyQueue<String> q = new MyQueue<>();

q.add("a");
q.add("b");
q.remove(); // should be "a", and is "a".
q.add("c");
q.remove(); // should be "b", but is "c".
q.remove(); // should be "c", but is "b".

Is not correct, at least when I traced the code.

The OP's implementation will never have the issue he mentioned. So here is the simple way of explaining the code.

-Create 2 stacks (newStack and oldStack).
-Always put new element into the newStack.
-When remove, always check if the oldStack is empty, 
if not, move everything from newStack to oldStack. 
(Now, the oldest element is on the top of the oldStack). 
Because we move everything from the newStack, now it is empty. 
Note that we need to empty the oldStack first before we move elements from newStack again.