【数据结构】队列的实现 --- 数组、链表

队列：

      一种先进先出的数据结构

基本操作：

• 入队： 加入元素至队尾
• 出队：从队头取出元素
• 判空：队列是否为空
• 判满：队列是否为满

实现：（以数组实现）

public class ArrayQueue 
{
	private int data[];
	private int head;      //队头
	private int tail;      //队尾
	private int count;
	
	public ArrayQueue()
	{
		this.data=new int[10];    //默认队列大小为10
		this.head=this.tail=0;
		this.count=0;
	}
	public ArrayQueue(int size)
	{
		this.data=new int[size];
		this.head=this.tail=0;
		this.count=0;
	}
	//入队
	public boolean inQueue(int num)
	{
		//队列满时自动扩容
		if(this.count==this.data.length)    
		{
		   int t[]=new int[this.data.length*2];
		   for(int i=0;i<this.count;i++)      //拷贝原队列，按原序存入新数组的前面部分 
		   {
			   this.head=(this.head+1)%this.data.length;
			   t[i]=this.data[this.head];
		   }
		   this.head=-1;           //重置队头
		   this.tail=this.count-1;  //重置队尾
		   this.data=t;
		}
	     this.tail=(this.tail+1)%this.data.length;  //新元素加入队尾
		 this.data[this.tail]=num;
		 this.count++;
		 return true;
		}
	//出队
	public int outQueue()
	{
		if(this.count==0) return -1;
	    this.head=(this.head+1)%this.data.length;
	    this.count--;
		return this.data[this.head];
				
	}
	//判空
	public boolean isEmpty()
	{
		return this.count==0;
	}
	//判满
	public boolean  isFull()
	{
		return this.count==this.data.length;
	}
	//记录队列中元素个数
	public int size()
	{
		return this.count;
	}


}

以链表实现：

public class LinkedQueue 
{
	private Node head;
	private Node tail;
	private int count;
	
	public LinkedQueue()
	{
		this.head=this.tail=null;
		this.count=0;
	}
	
	public boolean inQueue(int num)
	{
		Node p=new Node(num);
		if(this.head==null)
			  this.head=this.tail=p;
		else
		{
			this.tail.next=p;
			this.tail=p;
			
		}
		 this.count++;
		 return true;
	}
	
	public int outQueue()
	{
		if(this.head==null) return -1;
		int num=this.head.data;
		this.head=this.head.next;
		this.count--;
		return num;
				
	}
	
	public boolean isEmpty()
	{
		return this.head==null;
	}
	
	public int size()
	{
		return this.count;
	}

}

class Node{
	public int data;
	public Node next = null;
	
	Node(int data)
	{
		this.data = data;
		this.next = null;	
	}
}