Implement queue using two stacks

Question

Although it's a well-known algorithm, I thought to implement it from the perspective of a coding interview. I want to know if I can improve my code somehow. So, given the time constraint, is this a good enough solution to impress the interviewer?

class MyQueue { private Stack<Integer> s1; private Stack<Integer> s2; MyQueue() { s1 = new Stack<>(); s2 = new Stack<>(); } public void enqueue(int item) { s1.push(item); } private void move() { if (s1.isEmpty()) { throw new NoSuchElementException(); } else { while (!s1.isEmpty()) { s2.push(s1.pop()); } } } public int peek() { if (s2.isEmpty()) { move(); } return s2.peek(); } public int dequeue() { if (s2.isEmpty()) { move(); } return s2.pop(); } } public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner s = new Scanner(System.in); int N = s.nextInt(); MyQueue q = new MyQueue(); for (int i = 0; i < N; i++) { int op = s.nextInt(); switch (op) { case 1: int item = s.nextInt(); q.enqueue(item); break; case 2: q.dequeue(); break; case 3: System.out.println(q.peek()); break; default: System.out.println("Invalid option"); } } } } 

Answer 1

Maybe You could do better if you:

• Define an interface with complete JavaDoc.
• Make s1 and s2 final
• Write a JUnit-Test with constant testdata instead of reading input from keyboard. Do not use System.out.println in JUnit.

Answer 2

you can use the generics to support any kind of data type in the Queue

 class MyQueue<T> { private Stack<T> s1; private Stack<T> s2; 

Answer 3

You could replace the magic numbers in the case statements by constants with meaningfull names.

Answer 4

Unfortunately, it is not a queue. The sequence

push A push B pop push C pop pop 

outputs ACB instead of ABC. A push operation must copy s2 back to s1 before doing s1.push().

Answer 5

The logic is perfect . The case mentioned above will not occur

Operation Stack:s1 Stack:S2 output Comment Push A A ----------------------------------------------- Push B B A ------------------------------------------------ Pop A A s2 is empty hence will B copy whole 1 to s2 ------------------------------------------------ Push C C B ------------------------------------------------ Pop C B s2 is not empty not do any operation of move --------------------------------------------------- Pop C C S2 becomes empty hence will copy from s1 

Answer 6

ENQUEUE(Q, ELEMENT)

1) While stack1 is not empty, push everything from satck1 to stack2.

2) Push ELEMENT to stack1

3) Push everything back to stack1.

DQueue(q)

1) If stack1 is empty then error

2) Pop an item from stack1 and return it