patternjavaMinor
Class that implements a queue using two stacks
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:
Using two stacks to implement a queue is not a logical data structure as far as I am concerned. There are many better ways.
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.