国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

我理解的數據結構(三)—— 隊列(Queue)

hlcc / 3033人閱讀

摘要:我理解的數據結構三隊列一隊列隊列是一種線性結構相比數組,隊列對應的操作是數組的子集只能從一端隊尾添加元素,只能從另一端隊首取出元素隊列是一種先進先出的數據結構二數組隊列與循環隊列數組隊列如果你有看過我之前的文章不要小看了數組或者棧,你就會發

我理解的數據結構(三)—— 隊列(Queue) 一、隊列

隊列是一種線性結構

相比數組,隊列對應的操作是數組的子集

只能從一端(隊尾)添加元素,只能從另一端(隊首)取出元素

隊列是一種先進先出的數據結構(FIFO)

二、數組隊列與循環隊列 1. 數組隊列
如果你有看過我之前的文章不要小看了數組或者棧,你就會發現,自己封裝一個數組隊列是如此的輕松加愉快!

(1)先定義一個接口,接口中定義隊列需要實現的方法

public interface Queue {
    int getSize();
    boolean isEmpty();
    // 查看隊首元素
    E getFront();
    // 入隊
    void enqueue(E ele);
    // 出隊
    E dequeue();
}

(2)實現數組隊列

public class ArrayQueue implements Queue {
    
    // 這里的數組是在之前的文章中封裝好的,直接拿來用就好了
    private ArrayNew array;

    public ArrayQueue(int capacity) {
        array = new ArrayNew<>(capacity);
    }

    public ArrayQueue() {
        this(10);
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public void enqueue(E ele) {
        array.addLast(ele);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    @Override
    public String toString() {

        StringBuffer res = new StringBuffer();

        res.append(String.format("arrayQueue: size = %d, capacity = %d
", getSize(), getCapacity()));
        res.append("front [");

        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != getSize() - 1) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();

    }

}

(3)數組隊列的復雜度

方法 復雜度
enqueue O(1) 均攤
dequeue O(n)
front O(1)
getSize O(1)
isEmpty O(1)
這個時候我們會發現,在進行出隊操作的時候,數組隊列的復雜度是0(n),如果我們頻繁的進行出隊操作,那么其實數組隊列的效率是很低的,如何提升數組隊列的性能呢?這個時候我們就要用到循環隊列了。
2. 循環隊列隊列
循環隊列的原理:

dequeue時,不要在去除隊首元素時,把整體向前移動

維護 fronttailsize 這三個屬性

enqueue的時候tail++

dequeue的時候front++

(1)實現循環隊列

public class LoopQueue implements Queue {

    private E[] array;
    private int size;
    private int front;
    private int tail;

    public LoopQueue(int capacity) {
        // 我們需要浪費一個空間去判斷隊列是否已滿,所以需要把capacity + 1
        array = (E[])new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    // 返回用戶傳遞的隊列大小
    public int getCapacity() {
        return array.length - 1;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty. Can"t get front.");
        }

        return array[0];
    }

    @Override
    public void enqueue(E ele) {

        if (front == (tail + 1) % array.length) {
            // 擴展隊列長度為原長度2倍
            resize(getCapacity() * 2);
        }

        array[tail] = ele;
        size++;
        tail = (tail + 1) % array.length;
    }

    @Override
    public E dequeue() {

        if (isEmpty()) { // 隊列為空
            throw new IllegalArgumentException("Queue is empty. Can"t get dequeue.");
        }

        E ele = array[front];

        size--;
        array[front] = null;
        front = (front + 1) % array.length;

        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }

        return ele;

    }

    private void resize(int newCapacity) {
        E[] newArray = (E[]) new Object[newCapacity + 1];

        for (int i = 0; i < size; i++) {
            newArray[i] = array[(front + i) % array.length];
        }

        array = newArray;
        front = 0;
        tail = size;
    }

    @Override
    public String toString() {
        StringBuffer res = new StringBuffer();

        res.append(String.format("queue: size = %d, capacity = %d
", getSize(), getCapacity()));
        res.append("front [");

        // 循環條件,和循環增量都要注意下
        for (int i = front; i != tail; i = (i + 1) % array.length) {
            res.append(array[i]);

            if ((i + 1) % array.length != tail) {
                res.append(", ");
            }
        }
        res.append("] tail");

        return res.toString();
    }

}

(2)循環隊列的復雜度

方法 復雜度
enqueue O(1) 均攤
dequeue O(1) 均攤
front O(1)
getSize O(1)
isEmpty O(1)
三、用時間說話

(1)用時方法

public static double test(Queue q, int opCount) {

    // 納秒
    long startTime = System.nanoTime();

    Random random = new Random();

    for (int i = 0; i < opCount; i++) {
        q.enqueue(random.nextInt(Integer.MAX_VALUE));
    }
    for (int i = 0; i < opCount; i++) {
        q.dequeue();
    }

    // 納秒
    long endTime = System.nanoTime();

    return (endTime - startTime) / 1000000000.0;
}

(2)調用

// 十萬次入隊和十萬次出隊操作
int opCount = 100000;

ArrayQueue aq = new ArrayQueue<>();
double time1 = test(aq, opCount);
System.out.println(time1);

LoopQueue lq = new LoopQueue<>();
double time2 = test(lq, opCount);
System.out.println(time2);

(3)結果

14.635995113

0.054536447

這個就是算法和數據結構的力量!

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

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

相關文章

  • 理解數據結構)—— 隊列Queue

    摘要:我理解的數據結構三隊列一隊列隊列是一種線性結構相比數組,隊列對應的操作是數組的子集只能從一端隊尾添加元素,只能從另一端隊首取出元素隊列是一種先進先出的數據結構二數組隊列與循環隊列數組隊列如果你有看過我之前的文章不要小看了數組或者棧,你就會發 我理解的數據結構(三)—— 隊列(Queue) 一、隊列 隊列是一種線性結構 相比數組,隊列對應的操作是數組的子集 只能從一端(隊尾)添加元素,...

    wean 評論0 收藏0
  • 消息中間件——RabbitMQ(理解RabbitMQ核心概念和AMQP協議!

    摘要:后續介紹交換機,生產者直接將消息投遞到中。消息,服務器和應用程序之間傳送的數據,由和組成。也稱為消息隊列,保存消息并將它們轉發給消費者。主要是應為和有一個綁定的關系。 showImg(https://img-blog.csdnimg.cn/20190509221741422.gif); showImg(https://img-blog.csdnimg.cn/20190731191914...

    sihai 評論0 收藏0
  • 【Java實現】棧和隊列就是這么簡單

    摘要:一前言上一篇已經講過了鏈表實現單向鏈表了,它跟數組都是線性結構的基礎,本文主要講解線性結構的應用棧和隊列如果寫錯的地方希望大家能夠多多體諒并指正哦,如果有更好的理解的方式也希望能夠在評論下留言,讓大家學習學習二數據結構棧就是這么簡單數據結構 一、前言 上一篇已經講過了鏈表【Java實現單向鏈表】了,它跟數組都是線性結構的基礎,本文主要講解線性結構的應用:棧和隊列 如果寫錯的地方希望大家...

    Ethan815 評論0 收藏0
  • 學習JavaScript數據結構與算法(一):棧與隊列

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

    Flink_China 評論0 收藏0
  • 學習數據結構與算法之棧與隊列

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

    pingan8787 評論0 收藏0

發表評論

0條評論

hlcc

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<