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

╰+攻爆jí腚メ 2022-02-05 03:19 235阅读 0赞

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

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

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

//数组实现固定大小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]+" ");
    		}
    	}

注意队列满的判断条件。

小记。