基于数组和链表的队列实现

队列接口定义，和栈接口一样：

public interface Queue<Item> {

	/**
	 * 添加一个元素
	 * @param item
	 */
	public void push(Item item);
	
	/**
	 * 获取最后一个添加的元素，并将其从队列中删除
	 * @return
	 */
	public Item pop();
	
	/**
	 * 判断队列是否为空
	 * @return
	 */
	public boolean isEmpty();
	
	/**
	 * 获取队列当前的元素个数
	 * @return
	 */
	public int size();
	
}

基于数组的实现，关键是如何resize：

import java.util.Iterator;

import com.mycode.algorithms.stack.Stack;

/**
 * 基于数组的队列实现
 * @author imhuqiao
 */
public class ArrayQueue<Item> implements Queue<Item>,Iterable<Item> {

	private Item[] data = null;
	private int tail = -1;
	private int head = -1;
	private int count = 0;
	
	public ArrayQueue(){
		this(10);
	}
	
	public ArrayQueue(int initLength){
		data = (Item[]) new Object[initLength];
	}
	
	@Override
	public void push(Item item) {
		if(size()==data.length){
			resize(data.length*2);
		}
		data[++tail] = item;
		if(head==-1){
			head = 0;
		}
		count++;
		print();
	}
	
	@Override
	public Item pop() {
		if(isEmpty()){
			return null;
		}
		Item item = data[head];
		data[head] = null;
		head++;
		if(size() > 0 && size() == data.length/4) resize(data.length/2);
		print();
		count--;
		return item;
	}
	
	private void print(){
		System.out.print("[");
		for(Item d : data){
			System.out.print(d+",");
		}
		System.out.println("],tial="+tail+",head="+head);
	}


	@Override
	public boolean isEmpty() {
		return size()==0;
	}

	@Override
	public int size() {
		return count;
	}

	@Override
	public Iterator<Item> iterator() {
		return new ArrayStackIterator();
	}
	
	
	private void resize(int length){
		Item[] newdata = (Item[]) new Object[length];
		int x = 0;
		//System.out.println("resize from "+ size()+" to "+length);
		for(int i = head;i<=tail;i++){
			newdata[x++] = data[i];
			data[i] = null;
		}
		data = newdata;
		head = 0;
		tail = x==0 ? x : x-1;
	}
	
	class ArrayStackIterator implements Iterator<Item>{
		private int i = tail;
		private int j = head;
		@Override
		public boolean hasNext() {
			return i>=j;
		}

		@Override
		public Item next() {
			Item result = data[j++];
			return result;
		}

		@Override
		public void remove() {
			
		}
	}
}

基于链表的实现，原理和栈一致，只是多了一个记录尾部的变量，push的时候不是替换头而是接在尾巴上：

import java.util.Iterator;

import com.mycode.algorithms.stack.Stack;

/**
 * 基于数组的队列实现
 * @author imhuqiao
 */
public class ArrayQueue<Item> implements Queue<Item>,Iterable<Item> {

	private Item[] data = null;
	private int tail = -1;
	private int head = -1;
	private int count = 0;
	
	public ArrayQueue(){
		this(10);
	}
	
	public ArrayQueue(int initLength){
		data = (Item[]) new Object[initLength];
	}
	
	@Override
	public void push(Item item) {
		if(size()==data.length){
			resize(data.length*2);
		}
		data[++tail] = item;
		if(head==-1){
			head = 0;
		}
		count++;
		print();
	}
	
	@Override
	public Item pop() {
		if(isEmpty()){
			return null;
		}
		Item item = data[head];
		data[head] = null;
		head++;
		if(size() > 0 && size() == data.length/4) resize(data.length/2);
		print();
		count--;
		return item;
	}
	
	private void print(){
		System.out.print("[");
		for(Item d : data){
			System.out.print(d+",");
		}
		System.out.println("],tial="+tail+",head="+head);
	}


	@Override
	public boolean isEmpty() {
		return size()==0;
	}

	@Override
	public int size() {
		return count;
	}

	@Override
	public Iterator<Item> iterator() {
		return new ArrayStackIterator();
	}
	
	
	private void resize(int length){
		Item[] newdata = (Item[]) new Object[length];
		int x = 0;
		//System.out.println("resize from "+ size()+" to "+length);
		for(int i = head;i<=tail;i++){
			newdata[x++] = data[i];
			data[i] = null;
		}
		data = newdata;
		head = 0;
		tail = x==0 ? x : x-1;
	}
	
	class ArrayStackIterator implements Iterator<Item>{
		private int i = tail;
		private int j = head;
		@Override
		public boolean hasNext() {
			return i>=j;
		}

		@Override
		public Item next() {
			Item result = data[j++];
			return result;
		}

		@Override
		public void remove() {
			
		}
	}
}

测试代码：

	@Test
	public void testArrayQueue(){
		Queue<String> as = new ArrayQueue<String>(1);
		as.push("a");
		as.push("b");
		as.push("c");
		as.push("d");
	    as.push("e");
		Assert.assertEquals("a",as.pop());
		Assert.assertEquals("b",as.pop());
		String res = "";
		for(String str : as){
			res += str;
		}
		Assert.assertEquals("cde",res);
	}

	@Test
	public void testLinkQueue(){
		Queue<String> as = new LinkQueue<String>();
		as.push("a");
		as.push("b");
		as.push("c");
		as.push("d");
	    as.push("e");
		Assert.assertEquals("a",as.pop());
		Assert.assertEquals("b",as.pop());
		String res = "";
		for(String str : as){
			res += str;
		}
		Assert.assertEquals("cde",res);
	}