3
\$\begingroup\$

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());
    }

}
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – rcgldr May 27 '16 at 0:49
  • \$\begingroup\$ So my solution is the best in terms of time complexity with two stacks? \$\endgroup\$ – Mona Jalal May 27 '16 at 0:59
  • \$\begingroup\$ that is one missleading class name... \$\endgroup\$ – Dbl May 27 '16 at 1:35
5
\$\begingroup\$

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();
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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