數(shù)據(jù)結(jié)構(gòu)與算法——隊(duì)列

OldPanda 發(fā)布于2019-08-16 15:51 / 632人閱讀

摘要：概述前面說完了棧，接下來再看看另一種很基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列。很明顯，隊(duì)列的操作也是受限的，插入元素入隊(duì)只能在隊(duì)尾，刪除元素出隊(duì)只能在隊(duì)頭。這時(shí)候我們需要進(jìn)行數(shù)據(jù)搬移，性能會受到影響，而循環(huán)隊(duì)列解決了這個(gè)問題。

1. 概述

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

2. 隊(duì)列實(shí)現(xiàn)

和棧一樣，隊(duì)列也有兩種實(shí)現(xiàn)方式，使用數(shù)組實(shí)現(xiàn)的隊(duì)列叫做順序隊(duì)列，使用鏈表實(shí)現(xiàn)的隊(duì)列叫做鏈?zhǔn)疥?duì)列。這里我實(shí)現(xiàn)了鏈?zhǔn)疥?duì)列，你也可以根據(jù)其思想使用數(shù)組來實(shí)現(xiàn)。

public class LinkedListQueue {
    
    private Node head;//隊(duì)頭節(jié)點(diǎn)指針
    private Node tail;//隊(duì)尾節(jié)點(diǎn)指針
    private int size;//隊(duì)列中元素個(gè)數(shù)

    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    //入隊(duì)
    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;
    }
    
    //出隊(duì)列
    public String dequeue() {
        if(head == null) return null;//隊(duì)列為空
        
        String result = head.getData();
        
        head = head.next;
        this.size --;
        return result;
    }
    
    //定義鏈表節(jié)點(diǎn)
    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. 循環(huán)隊(duì)列

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

循環(huán)隊(duì)列就是將數(shù)組首尾相連，形成了一個(gè)環(huán)形：

如上圖，當(dāng)指針 tail 到達(dá)數(shù)組末尾的時(shí)候，并不進(jìn)行數(shù)據(jù)搬移，而是直接將指針向前移，到達(dá)了 0 這個(gè)位置。在進(jìn)行一次入隊(duì)，就變成了下面的樣子：

可以看到，循環(huán)隊(duì)列判斷空的條件是 head == tail，而怎么判斷隊(duì)列滿呢？答案是（tail + 1）== head 的時(shí)候，隊(duì)列就滿了，不能看出循環(huán)隊(duì)列實(shí)際上浪費(fèi)了一個(gè)存儲空間。下面我給出了循環(huán)隊(duì)列的代碼實(shí)現(xiàn)：

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);
    }
    
    //入隊(duì)列
    public boolean enqueue(String value) {
        if((tail + 1) % items.length == head) return false;//隊(duì)列已滿
        
        items[tail] = value;
        //head 和 tail 指針的移動不是簡單的加減1了
        tail = (tail + 1) % items.length;
        this.size ++;
        
        return true;
    }

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

    //打印隊(duì)列中數(shù)據(jù)
    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();
    }
}