/// とてもシンプルな単方向リンクリスト（空リストはnullで表す）
/// LispとかHaskellとかOCamlだと組み込みであるやつ
class List<E>
{
	final E       car;
	final List<E> cdr;

	List(E car, List<E> cdr)
	{
		this.car = car;
		this.cdr = cdr;
	}

	List<E> reverse()
	{
		List<E> rev = null;
		for(List<E> p=this; p!=null; p=p.cdr)
			rev = new List<E>(p.car, rev);
		return rev;
	}
}

/// Queue<List<E>> を実装に使っている Queue<E>
class Queue<E>
{
	final private List<E>        head;
	final private Queue<List<E>> middle;
	final private List<E>        tail;

	final private int hmSize;
	final private int  tSize;

	/// 空キューを作成
	public Queue() { head=tail=null; middle=null; hmSize=tSize=0; }

	/// 先頭要素を返す
	public E top()
	{
		return head.car;
	}

	/// 先頭要素を除いた残りのキューを返す
	public Queue<E> pop()
	{
		return new Queue<E>( head.cdr, middle, tail, hmSize-1, tSize );
	}

	/// 新しい要素をtailに突っ込んだキューを返す
	public Queue<E> push(E e)
	{
		return new Queue<E>( head, middle, new List<E>(e,tail), hmSize, tSize+1 );
	}

	/// サイズ
	public int size()
	{
		return hmSize + tSize;
	}

	/// コンストラクタ。不変条件を満たすようにメンバを設定
	///   invariant { hmSize >= tSize
	///               if hmSize>0 then h!=null }
	private Queue( List<E> h, Queue<List<E>> m, List<E> t, int hms, int ts )
	{
		if( hms >= ts ) // head+middle の方が tail より長い場合はほぼそのまま
		{
			if( hms>0 && h==null )
			{
				head   = m.top(); // h は埋めておく
				middle = m.pop();
			}
			else
			{
				head   = h;
				middle = m;
			}
			tail   = t;
			hmSize = hms;
			tSize  = ts;
		}
		else // tail の方が長い場合は tail を head+middle 側に突っ込む
		{
			if( h == null )
			{
				// 修正 --> http://d.hatena.ne.jp/NyaRuRu/20080510/p2#c
				if( m == null || m.size() == 0 )
				{
					head   = t.reverse();
					middle = null;
				}
				else
				{
					head   = m.top();
					middle = m.pop().push(t.reverse());
				}
			}
			else
			{
				head   = h;
				middle = (m==null ? new Queue<List<E>>() : m).push(t.reverse());
			}
			tail   = null;
			hmSize = hms + ts;
			tSize  = 0;
		}
	}
}

/**
いちおう適当な解説

純粋関数型キューの基本アイデアは
  ・Queue を head, tail の２つのリストで実装
  ・取り出しは head から、要素の挿入は tail に行うことで、破壊的代入なしでキューを実現
  ・head が空になったら head = tail.reverse() する
です。

これで普通に使ってる分には、pushもpopも「平均的には」定数時間で実現されるんですが、
ただ、これだとたまたま「tail.reverse() が起きる直前のキュー」に対してばっかり操作が
加えられる最悪の状況が起こりえて、そうすると定数時間でなくなってしまう。

そこで、
  ・head が空になるより早めに、head.length < tail.length になったら
    「遅延評価で」head = head.append(tail.reverse()) する
という改良案が知られています。
~~~ このファイルの実装は遅延評価してないので、実は全然実用的には意味ないです。(^^; ~~~
遅延評価なのでtail.reverse()を呼んでからそれが実際に実行されるまでのあいだに
元々のheadの長さ分のタイムラグができて、そこで平均計算時間をうまく吸収できる
仕組み（詳細略）なのです。

ここでさらに
  ・reverse は仕方ないとしても append って要らなくね？
というアプローチをしてみるのが、ここで実装した "Bootstrapped Queue" になります。
実際にappendするんじゃなくて「appendされたはずのものリスト」みたいなのを覚えといて、
headが空になったらそこから取り出すだけでいいんじゃないか的アイデア。
この「appendされたはずのものリスト」の実装ですが、FIFO でなくてはならないので、
つまりここで Queue を再帰的に使ってみよう！！！！！！！！！ という感じなのでした。
*/


/// てすつ
public class BtsQ
{
	public static void main(String[] arg)
	{
		Queue<Integer> q = new Queue<Integer>();

		java.util.Random rnd = new java.util.Random();
		java.util.Queue<Integer> referenceQ = new java.util.LinkedList<Integer>();

		for(int i=0; i!=100; ++i)
		{
			int set = rnd.nextInt(10)+5;
			for(int j=0; j!=set; ++j)
			{
				int e = rnd.nextInt(100);
				q = q.push( e );
				referenceQ.offer(e);
			}

			int get = rnd.nextInt(q.size());
			for(int j=0; j!=set; ++j)
			{
				int e1 = q.top();
				int e2 = referenceQ.poll();
				System.out.println( e1 + " " + e2 + (e1==e2 ? "" : "BUG!!!!!!!") );
				q = q.pop();
			}
		}

		while( q.size() > 0 )
		{
			int e1 = q.top();
			int e2 = referenceQ.poll();
			System.out.println( e1 + " " + e2 + (e1==e2 ? "" : "BUG!!!!!!!") );
			q = q.pop();
		}
		if( referenceQ.peek() != null )
			System.out.println( "BUG!!!!!!!" );

/*
		q = q.push(1);
		q = q.push(2);
		q = q.push(3);
		q = q.push(20);
		q = q.push(10);
		q = q.push(0);
		q = q.push(100);
		q = q.push(200);
		System.out.println( q.top() ); q = q.pop();
		System.out.println( q.top() ); q = q.pop();
		System.out.println( q.top() ); q = q.pop();
		System.out.println( q.top() ); q = q.pop();
		System.out.println( q.top() ); q = q.pop();
		System.out.println( q.top() ); q = q.pop();
		System.out.println( q.top() ); q = q.pop();
*/
	}
}