數據結構與算法——隊列

OldPanda 發布于2019-08-16 15:51 / 628人閱讀

摘要：概述前面說完了棧，接下來再看看另一種很基礎的數據結構，隊列。很明顯，隊列的操作也是受限的，插入元素入隊只能在隊尾，刪除元素出隊只能在隊頭。這時候我們需要進行數據搬移，性能會受到影響，而循環隊列解決了這個問題。

1. 概述

前面說完了棧，接下來再看看另一種很基礎的數據結構，隊列。顧名思義，隊列跟我們現實生活中的排隊很相似：例如我們在食堂排隊打飯，先來的先打到，后來的只能一次排在后面，不允許插隊。很明顯，隊列的操作也是受限的，插入元素（入隊）只能在隊尾，刪除元素（出隊）只能在隊頭。結合下面的圖就很容易理解了：

2. 隊列實現

和棧一樣，隊列也有兩種實現方式，使用數組實現的隊列叫做順序隊列，使用鏈表實現的隊列叫做鏈式隊列。這里我實現了鏈式隊列，你也可以根據其思想使用數組來實現。

public class LinkedListQueue {
    
    private Node head;//隊頭節點指針
    private Node tail;//隊尾節點指針
    private int size;//隊列中元素個數

    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    //入隊
    public boolean enqueue(String value) {
        Node node = new Node(value);
        if(tail == null) {
            head = tail = node;
            this.size ++;
            return true;
        }
        
        tail.next = node;
        tail = node;
        
        this.size ++;
        return true;
    }
    
    //出隊列
    public String dequeue() {
        if(head == null) return null;//隊列為空
        
        String result = head.getData();
        
        head = head.next;
        this.size --;
        return result;
    }
    
    //定義鏈表節點
    public static class Node{
        private String data;
        private Node next;

        public Node(String data) {
            this.data = data;
            this.next = null;
        }

        public String getData() {
            return data;
        }
    }
}

3. 循環隊列

在使用數組實現隊列的時候，會出現一個問題，就是隨著隊頭和隊尾指針的后移，就算數組中還有空間，也不能進行入隊操作了。這時候我們需要進行數據搬移，性能會受到影響，而循環隊列解決了這個問題。

循環隊列就是將數組首尾相連，形成了一個環形：

如上圖，當指針 tail 到達數組末尾的時候，并不進行數據搬移，而是直接將指針向前移，到達了 0 這個位置。在進行一次入隊，就變成了下面的樣子：

可以看到，循環隊列判斷空的條件是 head == tail，而怎么判斷隊列滿呢？答案是（tail + 1）== head 的時候，隊列就滿了，不能看出循環隊列實際上浪費了一個存儲空間。下面我給出了循環隊列的代碼實現：

public class CircularQueue {

    private String[] items;
    private int size;
    private int head;
    private int tail;
    
    public CircularQueue(int capacity) {
        this.items = new String[capacity];
        this.size = 0;
        this.head = 0;
        this.tail = 0;
    }
    
    public CircularQueue() {
        this(16);
    }
    
    //入隊列
    public boolean enqueue(String value) {
        if((tail + 1) % items.length == head) return false;//隊列已滿
        
        items[tail] = value;
        //head 和 tail 指針的移動不是簡單的加減1了
        tail = (tail + 1) % items.length;
        this.size ++;
        
        return true;
    }

    //出隊列
    public String dequeue() {
        if(head ==  tail) return null;//隊列為空
        
        String result = items[head];
        head = (head + 1) % items.length;
        this.size --;
        
        return result;
    }
    
    //隊列中元素個數
    public int size() {
        return size;
    }

    //打印隊列中數據
    public void print() {
        int h = head;
        int t = tail;
        
        while(h != t) {
            System.out.print(items[h] + "  ");
            h = (h + 1) % items.length;
        }
        System.out.println();
    }
}

云服務器 GPU云服務器算法與數據結構數據結構與算法數據結構與算法教程數據結構與算法答案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73733.html

你與解決“緩存污染”只差這篇文章的距離

摘要：如果處理不得當，就會造成緩存污染問題。解決緩存污染的算法算法，英文名，字面意思就是最不經常使用的淘汰掉算法，是通過數據被訪問的頻率來判斷一個數據的熱點情況。分析降低了緩存污染帶來的問題，命中率比要高。微信公眾號：IT一刻鐘大型現實非嚴肅主義現場一刻鐘與你分享優質技術架構與見聞，做一個有劇情的程序員關注可第一時間了解更多精彩內容，定期有福利相送喲。 showImg(https://s...

shadowbook 2019-08-06 13:41 評論0 收藏0
學習數據結構與算法之棧與隊列

摘要：于是翻出了機房里的這本學習數據結構與算法開始學習程序員的基礎知識。這本書用了我最熟悉的來實現各種數據結構和算法，而且書很薄，可以說是一本不錯的入門教程。隊列在頭部刪除元素，尾部添加元素。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構與算...

pingan8787 2019-08-20 18:37 評論0 收藏0
學習JavaScript數據結構與算法（一）：棧與隊列

摘要：之數組操作接下來就是數據結構的第一部分，棧。以字符串顯示棧中所有內容方法的實現說明需要往棧中添加新元素，元素位置在隊列的末尾。的前端樂園原文鏈接寒假前端學習學習數據結構與算法，棧與隊列本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第...

Flink_China 2019-08-19 17:23 評論0 收藏0
每周一練之 數據結構與算法（Queue）

摘要：與堆棧區別隊列的操作方式和堆棧類似，唯一的區別在于隊列只允許新數據在后端進行添加。移除隊列的第一項，并返回被移除的元素。三使用隊列計算斐波那契數列的第項。前兩項固定為，后面的項為前兩項之和，依次向后。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第二周的練習題，這里補充下咯，五一節馬上就要到了，自己的...

anquan 2019-08-23 17:10 評論0 收藏0
Java數據結構與算法[原創]——隊列

摘要：前言數據結構與算法專題會不定時更新，歡迎各位讀者監督。隊列和棧類似，也是一個遵循特殊規則約束的數據結構。將沒有元素的隊列稱之為空隊，往隊列中插入元素的過程稱之為入隊，從隊列中移除元素的過程稱之為出隊。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本文介紹數據結構中的隊列（queue）的概念、存儲結構、隊列的特點...

韓冰 2019-08-19 10:43 評論0 收藏0
[ JavaScript ] 數據結構與算法 —— 隊列

摘要：而且目前大部分編程語言的高級應用都會用到數據結構與算法以及設計模式。隊列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊列的末尾。前言 JavaScript是當下最流行的編程語言之一，它可以做很多事情：數據可視化（D3.js，Three.js，Chart.js）; 移動端應用(React Native,Weex,AppCan,Flutter,Hybrid App,小程...

Yi_Zhi_Yu 2019-08-23 15:05 評論0 收藏0