# Implement queue using two stacks

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

}
}


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.

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;


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

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

• I need to check because I did pass all my tests on Hackerrank. – CodeYogi Dec 20 '16 at 2:38

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


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

• By this solution enqueue operation becomes more cos-tier , as each and every time need to copy from stack1 to stack2 and most of time stack is not empty. So It is optimal to make the DQueue operation costier as presented in solution. – Damaji kalunge Dec 20 '16 at 15:10
• could you please explain what you are doing and how it works (please edit into the answer) thank you – Malachi Dec 20 '16 at 15:47