HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Class that implements a queue using two stacks

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
classimplementstwostacksthatusingqueue

Problem

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

public class MyQueue {
  Stack stackNewest, stackOldest;

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

  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
  }
}

Solution

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 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.

Code Snippets

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".

Context

StackExchange Code Review Q#54762, answer score: 6

Revisions (0)

No revisions yet.