26 Jan 2014

Stack & Queues: Stack using Queues

Problem Statement: 
         Implement Stack using two Queues.

Fig: Stack And Queue
Source Code LINK
Solution: 
    We will be using two queues for achieving efficiency instead of one.
The code that we will be implementing will have pop operation with some over head compared to push.
Assume we two queues Q1 and Q2.

Push : enqueue item to Q1

Pop:  dequeue all the element from Q1 and  and enqueue them to Q2 except the last element, Flip the name of the queues and return the element of Q1.

            Below is the implementation of PUSH and POP operations:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
	 * Push operation of Stack
	 * Item pushed into Queue1
	 */
	@Override
	public void push(Integer item) {
		System.out.println("Push : "+item);
		queue1.offer(item);
	}

	/**
	 * Pop operation of Stack
	 * last item of queue1 is returned, 
	 * order is reversed using queue2
	 */
	@Override
	public Integer pop() {
		Integer item=null;
		if(!queue1.isEmpty())
		{
			while (!queue1.isEmpty()) 
			{
				 item=queue1.poll();
				if(!queue1.isEmpty())
					queue2.add(item);
			}
			flip();
		}
		else
			System.out.println("Stack is Empty");
		System.out.println("Poped : "+ item);
		return item;
	}

The PEEK operation will be similar to POP operation, but all the items of Q1 will be pushed to Q2 , and names will be swapped.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/**
	 * Peek operation, similar to pop , 
	 * with slight modification
	 */
	@Override
	public Integer peek() {
		Integer item=null;
		while (!queue1.isEmpty()) {
			 item=queue1.poll();
				queue2.add(item);
		}
		flip();
		System.out.println("Peek : "+ item);
		return item;
	}

Other implementations is given below


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
         @Override
	public boolean isEmpty() {
		return queue1.isEmpty();
	}

	/**
	 * Flipping of Queues
	 */
	public void flip(){
		Queue<Integer> tQueue=  queue1;
		queue1=queue2;
		queue2 = tQueue;
	}

Please post your suggestions if any.

References: Stackoverflow
Happy Coding!! :)

1 comment: