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

• Tobias Otto: This is not for a interview, but a solution of a hackerrank challenge. hackerrank.com/challenges/maximum-element

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

• CodeYogi: I need to check because I did pass all my tests on Hackerrank.

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

• Damaji kalunge: 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.
• Malachi: could you please explain what you are doing and how it works (please edit into the answer) thank you