• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • 數據結構(三)——基于數組的隊列和循環隊列

    標簽: 循環隊列  隊列  Queue

        隊Queue也是一個線性的存儲結構,原則是先入先出(FIFO)區別于棧的先進后出。就類似與排隊買票,先進入隊列的就先買票出列;入隊在一端操作(隊尾),出隊只能在另一端操作(隊首);

        一個隊列的基本操作就是入隊,出隊,獲取隊列大小,判斷是否為空等等;這篇博客就是自己實現一個基于數組的隊列和循環隊列。

        根據上面的分析,創建一個Queue接口,提供入隊,出隊,判空等操作:

    public interface Queue<E> {             //使用泛型使得隊列可以存儲各種類型的元素
    	void enqueue(E e);		//入隊(從隊尾操作)
    	E dequeue();			//出隊,返回出隊的元素(從隊首操作)
    	public int getSize();	        //獲取隊列中元素的個數
    	boolean isEmpty();		//判斷隊列是否為空
    	E front();			//獲取隊首的元素
    }

    下面,基于數組實現一個隊列,來看看具體的方法怎么實現:

    為了實現隊列的可擴容,我們用于實現的數組是博客“數據結構(一)——封裝動態數組”中的動態數組;具體的原理可以查看之前的那篇博客,這里只貼代碼:

    package com.itheima.array;
    
    /**
     * @author GuoBaoYu
     *	使用泛型,可以存放任意類型的數據;
     */
    public class Array<E> {
    	private E[] data;   //內部是靜態數組
    	private int size;
    	
    	public Array(int capacity) {
    		data =(E[]) new Object[capacity];
    		size = 0;
    	}
    	
    	/**
    	 * 默認構造一個容量為10的數組
    	 */
    	public Array() {
    		this(10);
    	}
    	
    	public int getCapacity(){
    		return data.length;
    	}
    	
    	public boolean isEmpty(){
    		return size==0 ;
    	}
    	
    	public int getSize(){
    		return size;
    	}
    	
    	public void addLast(E element){
    		add(size, element);
    	}
    	
    	public void addFirst(E element){
    		add(0,element);
    	}
    	
    	//動態數組進行自動擴容和減少容量
    	private void resize(int newCapacity){
    		E[] newData = (E[]) new Object[newCapacity];
    		for(int i = 0; i < size;i++){
    			newData[i] = data[i];
    		}
    		data = newData;
    	}
    	
    	/**
    	 * @param index
    	 * @param element
    	 * 向指定的位置插入元素
    	 */
    	public void add(int index,E element){
    		if(size == getCapacity()){
    //			throw new IllegalArgumentException("AddLast is failed. Array is full.");
    //		之前如果數組空間滿了,拋出異常;現在進行擴容
    			int newCapacity = getCapacity()*2;
    			resize(newCapacity);
    		}
    		
    		if(index < 0 || index > size){
    			throw new IllegalArgumentException("Argument index is illegal.index is required index >=0 and index <= size. ");
    		}
    		
    		for(int i = size-1; i>=index; i--){
    			data[i+1] = data[i];
    		}
    		data[index] = element;
    		size++;
    	}
    
    	@Override
    	public String toString(){
    		StringBuilder builder = new StringBuilder();
    		builder.append(String.format("size = %d,capacity = %d\t", size,getCapacity()));
    		builder.append("[");
    		for(int i = 0; i < size; i++){
    			builder.append(data[i]);
    			if(i<size-1){
    				builder.append(",");
    			}
    		}
    		builder.append("]");
    		return builder.toString();
    	}
    	
    	public E get(int index){
    		if(index >=size || index <0){
    			throw new IllegalArgumentException("Argument index is illegal.");
    		}
    		return data[index];
    	}
    	
    	public void set(int index, E element){
    		if(index >=size || index <0){
    			throw new IllegalArgumentException("Argument index is illegal.");
    		}
    		data[index] = element;
    	}
    	
    	public boolean contains(E element){
    		for(int i =0; i <size;i++){
    			if(data[i].equals(element)){
    				return true;
    			}
    		}
    		return false;
    	}
    	
    	public E getFirst(){
    		return get(0);
    	}
    	
    	public E getLast(){
    		return get(size-1);
    	}
    	
    	public int find(E element){
    		for(int i=0 ; i < size; i++){
    			if(data[i].equals(element)){
    				return i;
    			}
    		}
    		return -1;
    	}
    	
    	//刪除index位置的元素,并返回刪除的元素的值
    	public E remove(int index){
    		if(index < 0 || index >= size){
    			throw new IllegalArgumentException("Remove failed.index is an illegal argument.");
    		}  
    		E element = data[index];
    		for(int i = index+1; i < size; i++){
    			data[i-1] = data[i];
    		}
    		size--;
    		
    		if(size <= getCapacity() /4 && data.length/2 !=0){
    			resize(getCapacity()/2);
    		}
    		return element;
    	}
    	
    	//刪除第一個元素
    	public E  removeFirst(){
    		return remove(0);
    	}
    	//刪除最后一個元素
    	public E removeLast(){
    		return remove(size-1);
    	}
    	
    	/**
    	 * @param element
    	 * @return
    	 * 刪除指定的數據
    	 */
    	public boolean removeElement(E element){
    		int find = find(element);
    		if(find!=-1){
    			remove(find);
    			return true;
    		}
    		return false;
    	}
    }

    基于這個動態數組Array,實現一個隊列:

    package com.itheima.queue;
    
    import com.itheima.array.Array;
    
    public class ArrayQueue<E> implements Queue<E>{
    	private Array<E> array;
    	
    	public ArrayQueue() {
    		array = new Array<E>(10);
    	}
    	
    	//允許用戶指定隊列的容量
    	public ArrayQueue(int capacity){   		  
    		array = new Array<E>(capacity);
    	}
    	
    	public int getCapacity(){
    		return array.getCapacity();
    	}
    	
    	//入隊從數組的尾部操作
    	public void enqueue(E e) {
    		array.addLast(e);     //入隊時隊列是否滿,是否觸發擴容操作在array.addLast()方法中考慮,所以這里直接調用;
    	}
    
    	//出隊從數組的首部操作
    	public E dequeue() {
    		return array.removeFirst();
    		//出隊時隊列是否為空,是否觸發縮容操作在array.removeFirst()方法中考慮,所以這里直接調用;
    	}
    
    	public int getSize() {
    		return array.getSize();
    	}
    
    	public boolean isEmpty() {
    		return array.isEmpty();
    	}
    
    	public E getFront() {
    		return array.getFirst();
    	}
    
    	@Override
    	public String toString() {
    		StringBuilder res = new StringBuilder();
    		res.append("ArrayQueue:");
    		res.append("front:[");
    		
    		for(int i = 0; i < array.getSize();i++){
    			res.append(array.get(i));
    			if(i < array.getSize()-1){
    				res.append(",");
    			}
    		}
    		res.append("] tail");
    		return res.toString();
    	}
    	
    	
    }

    一個簡單的測試:


    上面的這種實現方式可以實現隊列的動態擴容。但是依舊存在一定的缺陷:基于數組實現的隊列,在進行出隊操作時是調用了數組的removeFirst()方法,移除數組下標為0的元素,后面的每個元素向前移動一個位置,再進行size--,時間復雜度為o(n):過程如下:(第三步的size還要進行size--,標在4的位置,圖截錯了..這里聲明一下)



    為了解決這一點,在數組隊列的基礎上改進循環隊列:基本思路是,在進行入隊和出隊操作(主要為了出隊操作,不需要移動數組中元素的位置),只需要維護隊列(數組)的front(頭)和tail(尾)的值,出隊變成了O(1)的操作;


    使用這種方式的另一個好處是構成了循環隊列:什么是循環呢?

    當出現下面這種存儲情況時:


    看起來不能再入隊,tail不能再進行tail++了,因為tail指示的是隊尾的后面第一個空的位置;但是實際上并不是不能再入隊,而是可以把數組看成一個環,數組的前面還有空間,tail變為(tail+1)%8=0,tail指示在下標為0的空間!所以tail真正的操作應該是(tail+1)%數組長度;



    以上就是循環隊列的基本思想。下面是循環隊列的實現,是基于普通靜態數組的:

    package com.itheima.queue;
    
    import com.itheima.array.Array;
    
    /**
     * @author GuoBaoYu
     *
     * @param <E>
     * 循環隊列
     */
    public class LoopQueue<E> implements Queue<E> {
    	private E[] data;
    	private int front,tail;
    	private int size;   //隊列的元素的個數
    	
    	public LoopQueue(int capacity) {
    		//用戶想要存放capacity個數據,根據之前的原理分析,為了防止判空和判滿沖突,需要預留一個空間!
    		data = (E[]) new Object[capacity+1];
    		front = 0;
    		tail = 0;
    		size = 0;
    	}
    	
    	public LoopQueue() {
    		this(10);
    	}
    	
    	public int getCapacity(){
    		return data.length-1;
    	}
    	
    	/* (non-Javadoc)
    	 * @see com.itheima.queue.Queue#enqueue(java.lang.Object)
    	 * 入隊:
    	 * 	1.如果隊滿,調用resize()方法進行擴容;
    	 * 	2.把數據放入tail的位置
    	 * 	3.維護tail和size的值
    	 */
    	public void enqueue(E e) {
    		if( (tail+1)% data.length == front){  		//數組判滿;進行%data.length是為了讓數組循環起來
    
    			//TODO 隊列滿了以后進行擴容
    			resize(getCapacity() *2);
    		}
    		data[tail] = e;
    		tail = (tail+1)%data.length;
    		size++;
    	}
    
    	private void resize(int newCapacity) {
    		E[] newData = (E[]) new Object[newCapacity + 1];
    		for(int i= 0; i < size;i++){
    			newData[i] = data[(front+i)% data.length];
    		}
    		data = newData;
    		front = 0;
    		tail = size;
    	}
    
    	public E dequeue() {
    		if(isEmpty()){
    			throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
    		}
    		E ret = data[front];
    		data[front] = null;
    		front = (front+1)%data.length;
    		size--;
    		
    		if(size==getCapacity()/4 && getCapacity()/2!=0){
    			resize(getCapacity()/2);
    		}
    		return ret;
    	}
    
    	public int getSize() {
    		return size;
    	}
    
    	public boolean isEmpty() {
    		return front == tail;
    	}
    
    
    	public E front() {
    		if(isEmpty()){
    			throw new IllegalArgumentException("No elements in this queue.");
    		}
    		return data[front];
    	}
    
    	@Override
    	public String toString() {
    		StringBuilder res = new StringBuilder();
    		res.append("LoopQueue:");
    		res.append("front:[");
    		
    		for(int i = front; i != tail;i = (i+1)%data.length){
    			res.append(data[i]);
    			if((i +1)% data.length != tail){
    				res.append(",");
    			}
    		}
    		res.append("] tail");
    		return res.toString();
    	}
    	
    	
    }

    一個簡單的測試:


    可以看到,出隊的結果和使用removeFirst()達到的效果是一樣的;

    代碼中值得注意的地方在于自動調整容量的resize()方法的實現和遍歷隊列的toString()方法:


    在進行入隊時,先根據之前分析的條件,(tail+1)%data.length==front判斷是否隊滿,如果隊滿進行擴容。擴容的思路是將隊列數組的大小調整為原來的2倍,當然也可以是1.5倍,看個人了;當需要擴容時,數組中的元素可能是這樣存放的:


    要想調整為容量為16的數組,我們完全沒有必要還按這個順序存放數據,可以像下面這樣:


    相當于在擴容的同時對數據進行了整理;還是創建一個兩倍大小+1的數組,新數組的0位置對應原來的front,1對應front+1......

    位置都存在front的偏移,所以有了resize()代碼中:把data[(front+i)%data.length]賦值給newData[i]


    最后更改data的指向,維護新數組的front和tail的值;如此實現擴容!當然resize()方法只是傳遞了一個新的容量作為參數;在enqueue()方法中傳遞一個大的新容量作為擴容;當出隊很多數據后可以傳遞一個小的容量,進行縮容。

    在覆蓋toString()方法時,和之前的從下標為0開始遍歷不同,變為從front開始遍歷,直到遍歷到最后一個元素,也需要注意一下。

    以上就是一個循環隊列的實現,把出隊操作的時間復雜度降為了O(1)。

    下面通過測試比較一下兩種隊列的效率:


    可以看到對10000個數據的出隊,LoopQueue循環隊列的效率遠高于ArrayQueue;


    版權聲明:本文為baoyu_G原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/baoyu_G/article/details/80945666

    智能推薦

    數據結構中隊列的實現(基于順序表循環隊列)

        在學習數據結構中,隊列也是一個重要的數據結構,我們今天來用基于順序表的隊列(Queue), 在基于順序表隊列如果是不循環的順序表,則在出隊列時,時間復雜度是O(n),所以我們用循環隊列來 實現,怎么解釋基于循環順序表的隊列呢? 我們上圖:   上圖是在不循環順序表中出隊。這樣不難看出時間復雜度不是很好。 所以我們來順序循環隊列,把順序表讓它循環利用。 看圖 上...

    數據結構(隊列和循環隊列的順序存儲結構)

    隊列的定義 隊列是一種先進先出(First In Last Out)的線性表,簡稱FIFO 允許插入的一端稱為隊尾,允許刪除的一端稱為隊頭 隊列接口Queue的定義 隊列的具體實現 測試類 隊列的順序存儲的缺點 循環隊列的順序存儲 具體實現 測試類...

    【數據結構】隊列(順序隊列、循環隊列、鏈隊列)

    文章目錄 前言 一、隊列的定義 二、隊列的順序存儲結構 1.順序隊列的定義 2.循環隊列定義 3.循環隊列的基本操作 三、隊列的鏈式存儲結構 1.鏈隊列的定義 2.鏈隊列的基本操作 前言 隊列也是一種線性表,其特殊性在于隊列的基本操作是線性表的子集。隊列按“先進先出”的規則進行操作,故稱其為操作受限的線性表。 一、隊列的定義 隊列(queue)是只允許在一端進行插入操作,在...

    【java】數據結構----隊列/循環隊列

    1.隊列的應用場景舉例 1.1隊列的簡要介紹 隊列是一個有序鏈表,可以用數組或是鏈表來實現。 遵循先入先出的原則。即:先存入隊列的數據,要先取出。后存入的要后取出 示意圖:(使用數組模擬隊列示意圖) 隊列本身是有序鏈表,若使用數組的結構來存儲隊列的數據,則隊列數組的聲明如下圖, 其中 maxSize 是該隊列的最大容量。 因為隊列的輸出、輸入是分別從前后端來處理,因此需要兩個變量 front及 r...

    數組刪除其中某個對象的方法

    數組刪除其中的對象或元素,在前端是比較常見的需求。 我現在比較常用的方法如下: 這種方法只適合刪除具有唯一標識的對象。 有沒有想要脫單的小伙伴,加入我們的脫單星球,認識更多優秀的小哥哥小姐姐 特此聲明,星球是免費的,但是創建星球的時候說是必須輸入金額,所以只能先私聊,我再加你免費加入!...

    猜你喜歡

    圖床搭建以及圖床工具的使用

    為什么要用圖床和圖床工具? 比較下面三種md中的圖片url地址(均免費),你會使用哪一種? 選1?由于是本地路徑,文檔分享后給其他人打開后很可能顯示圖片加載失敗。 選2?雖然分享后可以顯示圖片,但能保證加載速度? 選3?我肯定選這種,即兼容2的瀏覽器訪問,又能保證訪問速度。 這樣就可以回答上面的問題了!保證瀏覽器訪問要用圖床,保證加載速度要用圖床工具,又不花錢想想就開心。 除此之外本篇博客還會講解...

    并發編程理論篇

    一、必備知識回顧 計算機又叫電腦,即通電的大腦,發明計算機是為了讓他通電之后能夠像人一樣去工作,并且它比人的工作效率更高,因為可以24小時不間斷 計算機五大組成部分 控制器 運算器 存儲器 輸入設備 輸出設備 計算機的核心真正干活的是CPU(控制器+運算器=中央處理器) 程序要想被計算機運行,它的代碼必須要先由硬盤讀到內存,之后cpu取指再執行 并發 看起來像同時運行的就可以稱之為并發 并行 真正...

    Java LinkedHashMap

    Java LinkedHashMap 前言 Map是我們在實際使用過程中常用的集合,HashMap在Java的實際開發中出鏡率很高,它通過hash算法實現了高效的非線程安全的集合,它有一個缺點就是,用戶插入集合的數據時無序,在我們需要一些有序的map的時候,我們就需要引入另外一個集合:LinkedHashMap。 LinkedHashMap是一個有序的非線程安全的集合,它是HashMap的子類,基...

    Spark Streaming處理文件(本地文件以及hdfs上面的文件)

    標題介紹文件流之前先介紹一下Dstream 下面是來自官網一段的說明,Discretized Streams或DStream是Spark Streaming提供的基本抽象。它表示連續的數據流,可以是從源接收的輸入數據流,也可以是通過轉換輸入流生成的已處理數據流。在內部,DStream由一系列連續的RDD表示,這是Spark對不可變的分布式數據集的抽象(有關更多詳細信息,請參見Spark編程指南)。...

    《痞子衡嵌入式半月刊》 第 8 期

    痞子衡嵌入式半月刊: 第 8 期 這里分享嵌入式領域有用有趣的項目/工具以及一些熱點新聞,農歷年分二十四節氣,希望在每個交節之日準時發布一期。 本期刊是開源項目(GitHub: JayHeng/pzh-mcu-bi-weekly),歡迎提交 issue,投稿或推薦你知道的嵌入式那些事兒。 上期回顧 :《痞子衡嵌入式半月刊: 第 7 期》 嘮兩句 今天是小滿,小滿節氣意味著進入了大幅降水的雨季。痞子...

    精品国产乱码久久久久久蜜桃不卡