算法(第四版)-1.3.14答案

算法(第四版)-1.3.14 编写一个类ResizingArrayQueueOfStrings，使用定长数组实现队列的抽象，然后扩展实现，使用调整数组的方法突破大小的限制。

问题

编写一个类ResizingArrayQueueOfStrings，使用定长数组实现队列的抽象，然后扩展实现，使用调整数组的方法突破大小的限制。

答案

package _1_3;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 非静态内部类因为是了属于对象的，所以初始化时需要先初始化一个外部类实例对象， 然后使用此对象调用内部类的构造方法。
 * 静态内部类属于类本身，初始化时直接使用外部类调用静态内部类的构造方法即可。
 * 
 * @author 煨酒小童
 *
 */
public class _1_3_14 {
	public static void main(String[] args) {
		_1_3_14.Resizingarrayqueueofstrings<Integer> haha = new _1_3_14().new Resizingarrayqueueofstrings<Integer>();
		for (int i = 1; i <= 10; i++) {
			haha.enqueue(i);
		}
		for (int i : haha) {
			System.out.println(i);

		}

	}

	class Resizingarrayqueueofstrings<Item> implements Iterable<Item> {
		private int head;
		private int tail, N;
		private Item a[];

		public Resizingarrayqueueofstrings() {
			a = (Item[]) new Object[2];
			head = 0;
			tail = 0; // 放置下一个物品
			N = 0; // 队列大小
		}

		public int size() {
			return N;
		}

		public boolean isEmpty() {
			return N == 0;
		}

		public void enqueue(Item temp) {
			if (tail == a.length - 1) {
				resize(2 * a.length);
			}
			a[tail++] = temp;
			N++;
		}

		private void resize(int num) {
			Item[] temp = (Item[]) new Object[num];
			int haha = 0;
			for (int i = head; i <= tail - 1; i++) {
				temp[haha++] = a[i];
				a[i] = null;
			}
			head = 0;
			tail = N;
			a = temp;
		}

		public Item dequeue() {
			if (N == 0)
				throw new NoSuchElementException();
			Item temp = a[head];
			a[head] = null;
			head++;
			if (head > a.length / 2 + 1) {
				resize(a.length / 2);
			}
			N--;
			return temp;
		}

		public Item peek() {
			int temp = head;
			while (temp < tail)
				return a[temp++];
			return null;
		}

		@Override
		public Iterator<Item> iterator() {

			return new ReverseArrayIterator();
		}

		private class ReverseArrayIterator implements Iterator<Item> {
			private int i = 0;
			private int start = head; // 这里迭代时不能改变队头，要一个临时变量指向对头

			@Override
			public boolean hasNext() {

				return i < N;
			}

			@Override
			public Item next() {
				i++;
				return a[start++];

			}

		}

	}
}