Queue implementation using two stacks

Question

Here's my code and I want to know if there's a better method for doing so. While the question has stated two stacks I wonder if we could do only with one as well?

/**
 * Created by mona on 5/26/16.
 */
import java.util.Stack;
//Implement queue using two stacks
public class QueueViaStacks {
 private int size=0;
 private Stack<Integer> firstStack = new Stack<>();
 private Stack<Integer> secondStack = new Stack<>();
 public void add(int item) {
 while (!firstStack.isEmpty()) {
 secondStack.push(firstStack.pop());
 }
 secondStack.push(item);
 while (!secondStack.isEmpty()) {
 firstStack.push(secondStack.pop());
 }
 size++;
 }
 public int remove() {
 size--;
 return firstStack.pop();
 }
 public int size() {
 return size;
 }
 public static void main(String[] args) {
 QueueViaStacks queue = new QueueViaStacks();
 queue.add(1);
 queue.add(2);
 queue.add(3);
 queue.add(4);
 queue.add(5);
 System.out.println(queue.remove());
 System.out.println(queue.size());
 System.out.println(queue.remove());
 System.out.println(queue.size());
 }
}

• rcgldr: Queues are typically FIFO (first in first out), stacks are LIFO (last in first out), so a single stack (without any other data structures), can't be used.
• Mona Jalal: So my solution is the best in terms of time complexity with two stacks?
• Dbl: that is one missleading class name...

Answer 1

Your solution is kind of crappy time complexity wise, as adding elements without removing any takes quadratic time, as you reverse the full stack twice for every value added. The better algorithm (which I think is amortized constant time) for this problem is to have one stack for input, and another for output. add() simply pushes to the inputStack, while remove() tries to pop from the outputStack, except if it is empty, in which case it first reverses the inputStack onto the outputStack:

public class QueueViaStacks {
 private Stack<Integer> inputStack = new Stack<>();
 private Stack<Integer> outputStack = new Stack<>();
 public void add(int item) {
 inputStack.push(item);
 }
 public int remove() {
 if (outputStack.isEmpty()) {
 while (!inputStack.isEmpty()) {
 outputStack.push(inputStack.pop());
 }
 }
 return outputStack.pop();
 }
 public int size() {
 return inputStack.size() + outputStack.size();
 }
}