import org.junit.Test;
import static org.junit.Assert.*;
import java.util.ArrayList;
import static java.util.Collections.*;

public class solution {

	public static class Queue<T> {
		private ArrayList<T> data = new ArrayList<T>();
		private int size = 0;
		private int begin = 0;

		public boolean empty() {
			return size == 0;
		}

		public void pushBack(T item) {
			if (size + 1 > data.size()) {
				if (begin == 0) {
					data.addAll(nCopies(2 * (data.size() + 1), (T)null));
				} else {
					ArrayList<T> newData = new ArrayList<T>(2 * (data.size() + 1));
					int p1begin = begin;
					int p1len = size - begin;
					int p2begin = 0;
					int p2len = p1begin;

					newData.addAll(data.subList(p1begin, p1begin + p1len));
					newData.addAll(data.subList(p2begin, p2begin + p2len));
					newData.addAll(nCopies(data.size() + 1, (T)null));
					data = newData;
				}
				begin = 0;
			}

			int index = (begin + size) % data.size();
			data.add(index, item);
			size++;
		}

		public T popFront() {
			T result = data.get(begin);
			begin = (begin + 1) % data.size();
			size--;
			return result;
		}
	}

	public static class UnitTest {
		@Test
		public void test() {
			Queue<Integer> q = new Queue<Integer>();
			assertEquals(q.empty(), true);
			q.pushBack(1);
			q.pushBack(2);
			q.pushBack(3);
			assertEquals(q.empty(), false);

			assertEquals((int)q.popFront(), 1);
			assertEquals((int)q.popFront(), 2);
			assertEquals((int)q.popFront(), 3);
			assertEquals(q.empty(), true);

			q.pushBack(4);
			assertEquals(q.empty(), false);
			assertEquals((int)q.popFront(), 4);
			assertEquals(q.empty(), true);

			int in = 0;
			int out = 0;
			for (int i = 1; i < 100; i++) {
				for (int j = 0; j < i; j++) {
					q.pushBack(in);
					in++;
				}

				int x = q.popFront();
				assertEquals(x, out);
				out++;
			}
			while (!q.empty()) {
				int x = q.popFront();
				assertEquals(x, out);
				out++;
			}
		}
	}
}