Implement queue using two stacks

Implement a MyQueue class which implements a queue using two stacks.

My initial thoughts:
The first stack keep pushing in new items as the enqueue function. When dequeue, stack1 pops element and stack2 push that element in. That will rearrange the order of FILO to FIFO. After the transfering, the first element will be on the top of stack2 so we just pop that out. Then we moving the elements in stack2 back to stack1.

My initial codes:

import java.util.Stack;
public class Q3_5 {

	private Stack<Object> stack1 = new Stack<Object>();
	private Stack<Object> stack2 = new Stack<Object>();

	public void enqueue(Object item) {
		stack1.push(item);
	}

	public Object dequeue() {
		if(stack1.empty())
			return null;
		else {
			while(!stack1.empty())
				stack2.push(stack1.pop());
			Object item = stack2.pop();
			while(!stack2.empty())
				stack1.push(stack2.pop());
			return item;
		}
	}
}

Comments after running:
Not quite efficient for dequeue.

Solution:

public class MyQueue<T> {
	Stack<T> s1, s2;
	
	public MyQueue() {
		s1 = new Stack<T>();
		s2 = new Stack<T>();
	}

	public int size() {
		return s1.size() + s2.size();
	}

	public void add(T value) {
		s1.push(value);
	}

	public T peek() {
		if (!s2.empty()) return s2.peek();
		while (!s1.empty()) s2.push(s1.pop());
		return s2.peek();
	}

	public T remove() {
		if (!s2.empty()) return s2.pop();
		while (!s1.empty()) s2.push(s1.pop());
		return s2.pop();
	}
}

Comments: lazy implementation for peek() and pop(). Only move elements from stack1 to stack2 when needed.

Advertisements