隊列

2020-04-07 16:09:49來源:博客園 閱讀 ()

容器云強勢上線!快速搭建集群,上萬Linux鏡像隨意使用

隊列

隊列

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

使用數組模擬隊列

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: 隊列為空,不能出隊!

原文鏈接:https://www.cnblogs.com/moyuduo/p/12657160.html
如有疑問請與原作者聯系

標簽:for解決使用數組大小實現

版權申明:本站文章部分自網絡,如有侵權,請聯系:west999com@outlook.com
特別注意:本站所有轉載文章言論不代表本站觀點,本站所提供的攝影照片,插畫,設計作品,如需使用,請與原作者聯系,版權歸原作者所有

上一篇:【從零開始學Java筆記】為什么選擇Java(學習資料分享:java四大

下一篇:4 種分布式session解決方案

韩国三级在线看免费