隊列

隊列

隊列是用數組或鏈表實現的，遵循先進先出規則的一個有序列表

使用數組模擬隊列

public class ArrayQueue<T> {

	private Object[] arr;
	private int front;
	private int rear;
	private int capacity;
	
	public ArrayQueue() {
		this.capacity=10;
		this.front=-1;
		this.rear=-1;
		this.arr=new Object[this.capacity];
	}
	
	public ArrayQueue(int capacity) {
		this.capacity=capacity;
		this.front=-1;
		this.rear=-1;
		this.arr=new Object[this.capacity];
	}
	
	public boolean add(T t) {
		if(this.rear<this.capacity-1) {
			this.arr[++rear]=t;
			return true;
		}
		throw new RuntimeException("隊列已滿！");
	}
	
	public T remove() {
		if(this.rear==this.front) {
			throw new RuntimeException("隊列為空，不能出隊列！");
		}
		return (T)this.arr[++front];
	}
	
	public T poll() {
		if(this.rear==this.front) {
			return null;
		}
		return (T)this.arr[++front];
	}
	
	public T peek() {
		if(this.rear==this.front) {
			return null;
		}
		return (T)this.arr[++front];
	}
	
	
	
	@Override
	public String toString() {
		String str= "ArrayQueue [";
		for(int i=front+1;i<=rear;i++) {
			str+=this.arr[i]+" ";
		}
		return str+="]";
	}

	public static void main(String[] args) {
		ArrayQueue<Integer> queue=new ArrayQueue<>(4);
		queue.add(1);
		queue.add(2);
		queue.add(3);
		queue.add(4);
		System.out.println(queue);
		
		Integer remove1 = queue.remove();
		System.out.println(remove1);
		
		Integer remove2 = queue.remove();
		System.out.println(remove2);
		
		Integer remove3 = queue.remove();
		System.out.println(remove3);
		
		Integer remove4 = queue.remove();
		System.out.println(remove4);
		
		queue.add(5);
		
	}
}

輸出：
ArrayQueue [1 2 3 4 ]
1
2
3
4
Exception in thread "main" java.lang.RuntimeException: 隊列已滿！

分析：雖然隊列中的元素已經全部出隊，但是由於我們的隊列是使用數組模擬的，而且每次入隊的時候，頭指定都後移，當我們入隊次數增加，總有一時刻，頭指針指向數組最大下標，儘管我們有出隊，但是任然不能入隊元素，我們可以使用數組模擬迴圈隊列來解決這個問題

使用數組模擬迴圈隊列

分析

我們可以做這樣一個約定，在數組中空一個位置，當（rear+1）%capacity==front來表示隊滿，當front==rear時表示隊空

這個時候，那麼計算隊列中元素個數公式為：size=(rear+capacity-front)%capacity

public class CircleArrayQueue<T> {

	private Object[] arr;
	private int front;
	private int rear;
	private int capacity;
	
	public CircleArrayQueue() {
		this.capacity=10;
		this.front=0;
		this.rear=0;
		this.arr=new Object[this.capacity];
	}
	
	public CircleArrayQueue(int capacity) {
		this.capacity=capacity;
		this.front=0;
		this.rear=0;
		this.arr=new Object[this.capacity];
	}
	
	public boolean add(T t) {
		if((rear+1)%capacity==front) {//隊列已滿
			throw new RuntimeException("隊列已滿！");
		}
		//rear下標超出最大下標，那麼取模
		rear=(rear+1)%capacity;
		this.arr[rear]=t;
		return true;
	}
	
	public T remove() {
		if(this.rear==this.front) {
			throw new RuntimeException("隊列為空，不能出隊列！");
		}
		return (T)this.arr[++front];
	}
	
	public T poll() {
		if(this.rear==this.front) {
			return null;
		}
		return (T)this.arr[++front];
	}
	
	public T peek() {
		if(this.rear==this.front) {
			return null;
		}
		return (T)this.arr[++front];
	}
	
	public int size() {
		return (rear+capacity-front)%capacity;
	}
	
	@Override
	public String toString() {
		String str= "ArrayQueue [";
		int total=size();
		int index=front+1;
		for(int i=0;i<total;i++) {
			str+=arr[index]+" ";
			index=(index+1)%capacity;
		}
		return str+="]";
	}
	
	public static void main(String[] args) {
		CircleArrayQueue<Integer> queue=new CircleArrayQueue<>(4);
		//由於需要空一個，capacity為4也只能存放三個元素
		queue.add(1);
		queue.add(2);
		queue.add(3);
		System.out.println(queue);
		
		Integer remove = queue.remove();
		System.out.println(remove);
		
		queue.add(4);
		System.out.println(queue);
	}
}
輸出：
ArrayQueue [1 2 3 ]
1
ArrayQueue [2 3 4 ]

鏈隊列

使用節點來包裝值，好處是使用鏈表可以不用考慮大小的問題，隊列永遠不可能滿

public class LinkedQueue<T> {

	static class Node<T>{
		T val;
		Node next;
		public Node(T val, Node next) {
			super();
			this.val = val;
			this.next = next;
		}
		
		public Node(T val) {
			this.val=val;
		}
	}
	
	private int size;
	private Node<T> front;
	private Node<T> rear;
	
	public LinkedQueue() {
		this.size=0;
	}
	
	public void add(T t) {
		Node<T> node=new Node<T>(t);
		this.size++;
		if(rear==null) {
			rear=node;
			front=node;
		}
		rear.next=node;
		rear=node;
	}
	
	public T remove() {
		if(size<=0) {
			throw new RuntimeException("隊列為空,不能出隊！");
		}
		size--;
		Node<T> n=front;
		if(size==0) {
			front=null;
			rear=null;
			return n.val;
		}
		front=front.next;
		return n.val;
	}
	
	public T poll() {
		if(size<=0) {
			return null;
		}
		size--;
		Node<T> n=front;
		if(size==0) {
			front=null;
			rear=null;
			return n.val;
		}
		front=front.next;
		return n.val;
	}
	
	public T peek() {
		if(this.size<=0) {
			return null;
		}
		return front.val;
	}
	
	public int size() {
		return size;
	}
	
	@Override
	public String toString() {
		String str= "LinkedQueue [";
		Node<T> n=front;
		while(n!=null) {
			str+=n.val+" ";
			n=n.next;
		}
		str+="]";
		return str;
	}

	public static void main(String[] args) {
		LinkedQueue<Integer> queue =new LinkedQueue<>();
		queue.add(1);
		queue.add(2);
		queue.add(3);
		System.out.println(queue);
		
		Integer remove1 = queue.remove();
		System.out.println(remove1);
		
		Integer remove2 = queue.remove();
		System.out.println(remove2);
		
		Integer remove3 = queue.remove();
		System.out.println(remove3);
		
		queue.remove();
	}
}

輸出：
LinkedQueue [1 2 3 ]
1
2
3
Exception in thread "main" java.lang.RuntimeException: 隊列為空,不能出隊！