Q3

import Adt.Node;
import Adt.Queue;
public class Q3 {

	public static void main(String[] args) {
		Queue<Integer> q1 = new Queue<Integer>();
		q1.insert(2);
		q1.insert(5);
		q1.insert(6);
		q1.insert(9);
		q1.insert(1);
		q1.insert(3);
		q1.insert(7);

		System.out.println("before:");
		printQueue(q1);
		Queue<Integer>resQ =  middleQ(q1,3);
		printQueue(resQ);

	}

	public static Queue<Integer> middleQ(Queue<Integer> q, int m) {
		Queue<Integer> tmpQ = new Queue<Integer>();
		Queue<Integer> midQ = new Queue<Integer>();
		Queue<Integer> frst_midQ = midQ;

		int size = countQ(q);
		int middle = (size-m)/2;
		int val=0;
		for (int i = 0; i < size; i++) {
			val = q.remove();
			if(i>=middle && m>0) {
				midQ.insert(val);
				tmpQ.insert(val);
				m--;
			}
			else
				tmpQ.insert(val);
		}
		while(!tmpQ.isEmpty()) {
			q.insert(tmpQ.remove());
		}
		return midQ;

	}
	/*
	 * input - queue of integers
	 * return - size of queue
	 */
	public static int countQ(Queue<Integer> q) {
		Queue<Integer> tmp = new Queue<Integer>();
		int size = 0;
		while(!q.isEmpty()) {
			size++;
			tmp.insert(q.remove());
		}
		while(!tmp.isEmpty()) {
			q.insert(tmp.remove());
		}
		return size;
	}
	/*
	 * input - queue of integers
	 * output - print queue
	 */
	public static void printQueue(Queue<Integer> q) {
		Queue<Integer> tmp = new Queue<Integer>();
		System.out.print("    ");
		while(!q.isEmpty()) {
			System.out.print(q.head()+"|");
			tmp.insert(q.remove());
		}
		while(!tmp.isEmpty()) {

			q.insert(tmp.remove());
		}
		System.out.println("null");

	}
}