current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite
1

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
  }
}
share|improve this question
1  
a) Make the properties private. b) Keep the initialization with the declaration: Stack<T> stackNewest = new Stack<T>(); There is no reason to defer the initialization until later. – Bob Dalgleish Jun 19 '14 at 22:33
    
It seems overly complicated to implement it using two stacks. Was this a requirement of the question or a design choice? An array with two 'pointers' (indices) for head and tail is probably simplest (with a re-allocation if we ever need it to grow in size) – AlanT Jun 20 '14 at 9:16
    
What's wrong with Queue? – Emily L. Jun 20 '14 at 12:42
up vote 7 down vote accepted

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.

share|improve this answer
up vote 1 down vote 
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.

share|improve this answer
up vote 0 down vote

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.