Java实现简单顺序队列及循环队列

队列，就像流水线上的作业，先进先出，后进后出。

资源有限的场景如线程池、及数据库连接池就是用队列来实现的。

数组实现顺序队列，实现简单入队、出队操作；

//数组实现固定大小n的顺序队列；
public class QueueByArray {
	private Object[] array;
	private int head = 0;
	private int tail = 0;
	private int length;
	
	public QueueByArray(int n){
		//创建一个大小为n的数组队列；head、tail分别为队头、队尾下标；
		array = new Object[n];
		length = n;
	}
	
	//入队；
	public boolean enqueue(Object value){
		if(tail == length && head == 0)
			return false;
		if(tail == length && head != 0){
			//数据搬移;
			for(int i = head; i < length; i++){
				array[i - head] = array[i];
			}
			tail -= head;
			head = 0;			
		}
		
		array[tail] = value;	
		tail++;
		return true;
	}
	
	//出队；
	public Object dequeue(){
		if(head == tail)
			return null;
		return array[head++];
	}
	
	//打印输出；
	public void printAll(){
		for(int i = head; i < tail; i++){
			System.out.println(array[i]+" ");
		}
	}

为降低入队时数据搬移的时间复杂度，引入循环链表：

public class CircularQueue {
	private Object[] array;
	private int size;
	private int head = 0;
	private int tail = 0;
	
	public CircularQueue(int s){
		array = new Object[s];
		this.size = s;		
	}
	
	//入队;
	public boolean enqueue(Object val){
		if((tail + 1) % size == head){ //满了；
			return false;
		}else{
			array[tail] = val;
			tail = (tail + 1) % size;
			return true;
		}			
	}
	
	//出队；
	public Object dequeue(){
		if(head == tail){
			return null;
		}
		Object tmp = array[head];
		head = (head + 1) % size;
		return tmp;
	}
	
	//打印全部;
	public void printAll(){
		for(int i = head; i < tail; i++){
			System.out.print(array[i]+" ");
		}
	}

注意队列满的判断条件。

小记。