Q2_sol

import Adt.Queue;

public class Q2 {

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

		System.out.println("before:");
		printQueue(q1);
		System.out.println("after:");

		printQueue(minusBeforePlus(q1));
	}
	/*
	 *
	 */
	public static Queue<Integer> minusBeforePlus(Queue<Integer> q) {
		Queue<Integer> ngtv_q = new Queue<Integer>();
		Queue<Integer> pls_q = new Queue<Integer>();

		while(!q.isEmpty()) {
			int val = q.remove();
			if(val<0)
				ngtv_q.insert(val);
			else
				pls_q.insert(val);
		}
		while(!ngtv_q.isEmpty()) {
			q.insert(ngtv_q.remove());
		}
		while(!pls_q.isEmpty()) {
			q.insert(pls_q.remove());
		}
		return q;

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

	}
}