数据结构—队列

队列也是表，是一种基于**先进先出策略（FIFO）**的集合类型，我们可以利用数组或者链表来实现一个队列。先进先出策略是指按照任务产生的顺序来执行它们的策略，也可以描述成优先服务等待最久的，跟我们现实生活中的排队是同样的道理。

在应用程序中使用队列的主要原因是在用集合来保存元素的同时保存他们的相对顺序：使他们入列的顺序与出列的顺序相同。

基于链表实现队列

API:
Queue()//创建空队列
void enqueue(Item item)//添加一个元素
Item dequeue()//删除最早添加的元素
boolean isEmpty()//队列是否为空
int size()//队列中的元素数量

import java.util.Iterator;

public class MyQueue<Item> implements Iterable<Item> {
	private Node first;//对头节点
	private Node last;//队尾节点
	private int size;//队列中元素数量
	
	//节点内部类，包含元素和next链
	private class Node{
		Item item;
		Node next;
	}
	
	//isEmpty()判断队列是否为空
	public boolean isEmpty() {
		return size() == 0;
	}
	
	//将一个元素入栈
	public void enqueue(Item item) {
		Node oldLast = last;
		last = new Node();
		last.item = item;
		last.next = null;
		if (isEmpty()) {
			first = last;
		}else {
			oldLast.next = last;
		}
		size++;
	}
	
	public Item dequeue() {
		Item oldItem;
		oldItem = first.item; 
		first = first.next;
		if(isEmpty()) {
			last = null;
		}
		size--;
		return oldItem;	
	}
	
	public int size() {
		return size;
	}
	
	@Override
	public Iterator<Item> iterator() {
		
		
		return new QueueIterator();
	}
	
	private class QueueIterator implements Iterator<Item>{

		private Node current = first;
		
		@Override
		public boolean hasNext() {
			
			return current != null;
		}

		@Override
		public Item next() {
			Item item = current.item;
			current = current.next;
			return item;
		}
		
	}

}

测试用例：

public class Test {
	public static void main(String[] args) {
		MyQueue<Integer> myQueue = new MyQueue<Integer>();
		
		System.out.println("队列是否为空：" + myQueue.isEmpty());
		System.out.println("队列的元素数量：" + myQueue.size());
		
		//入队
		myQueue.enqueue(0);
		myQueue.enqueue(1);
		myQueue.enqueue(2);
		myQueue.enqueue(3);
		myQueue.enqueue(4);
		myQueue.enqueue(5);
		
		System.out.println("队列是否为空：" + myQueue.isEmpty());
		System.out.println("队列的元素数量：" + myQueue.size());
		
		//遍历队列
		System.out.print("遍历队列：");
		for (Integer integer : myQueue) {
			System.out.print(integer + " ");
		}
		
		//循环出队
		System.out.println();//换行
		System.out.print("循环出队：");
		while(myQueue.size() > 0) {
			System.out.print(myQueue.dequeue() + " ");
		}
 	} 
}

运行结果：

队列也是一种表，我们除了可以利用链表来实现队列，还可以利用数组来实现一个队列。