Home » Stacks & Queues(Use Me !!) » Implement queue using two stacks

Implement queue using two stacks

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.


<span style="font-family: Consolas, Monaco, monospace; font-size: 12px; line-height: 18px;">import java.util.Stack;</span>
<pre title="">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;
		}
	}
}</pre>
<strong>Comments after running:</strong>
 Not quite efficient for dequeue.

<strong>Solution:</strong>
<pre title="">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();
	}
}</pre>

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Website

arpit tak

arpit tak

I like JAVA . I code. I chill. I blog.I eat. I sleep. I dream.

Personal Links

View Full Profile →

Followers

%d bloggers like this: