Rumah  >  Artikel  >  Java  >  Analisis kod sumber Java ArrayQueue.

Analisis kod sumber Java ArrayQueue.

PHPz
PHPzke hadapan
2023-05-09 08:10:151139semak imbas

    Pelaksanaan dalaman ArrayQueue

    Sebelum bercakap tentang pelaksanaan dalaman ArrayQueue, mari kita lihat contoh penggunaan ArrayQueue:

    public void testQueue() {
        ArrayQueue<Integer> queue = new ArrayQueue<>(10);
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        System.out.println(queue);
        queue.remove(0); // 这个参数只能为0 表示删除队列当中第一个元素,也就是队头元素
        System.out.println(queue);
        queue.remove(0);
        System.out.println(queue);
    }
    // 输出结果
    [1, 2, 3, 4]
    [2, 3, 4]
    [3, 4]

    Pertama sekali, ArrayQueue dilaksanakan secara dalaman oleh tatasusunan kitaran, yang mungkin memastikan bahawa kerumitan masa menambah dan memadam data adalah sama, tidak seperti kerumitan masa ArrayList memadamkan data. Terdapat dua data integer ArrayQueue dan head di dalam tail, yang digunakan terutamanya untuk menunjuk ke kepala dan ekor baris gilir >

    Analisis kod sumber Java ArrayQueue.Oleh kerana ia adalah keadaan awal, nilai

    dan

    kedua-duanya sama dengan 0, menunjuk kepada data pertama dalam tatasusunan. Sekarang kita menambah 5 keping data ke head, maka susun atur memorinya akan seperti yang ditunjukkan di bawah: tailArrayQueue

    Analisis kod sumber Java ArrayQueue. Sekarang kita memadam 4 keping data, kemudian angka di atas pergi melalui 4 Selepas operasi pemadaman, susun atur data dalaman

    adalah seperti berikut:

    ArrayQueue

    Analisis kod sumber Java ArrayQueue. Dalam keadaan di atas, kami terus menambah 8 data, maka susun atur adalah seperti berikut:

    Analisis kod sumber Java ArrayQueue.Kita tahu bahawa apabila menambah data dalam gambar di atas, bukan sahaja ruang dalam separuh kedua tatasusunan digunakan, tetapi juga ruang yang tidak digunakan dalam separuh masa pertama boleh diteruskan, iaitu dalam

    Proses kitar semula dilaksanakan secara dalaman.

    ArrayQueueAnalisis kod sumber ArrayQueue

    Pembina

    public ArrayQueue(int capacity) {
        this.capacity = capacity + 1;
        this.queue = newArray(capacity + 1);
        this.head = 0;
        this.tail = 0;
    }
    
    @SuppressWarnings("unchecked")
    private T[] newArray(int size) {
        return (T[]) new Object[size];
    }

    Kod pembina di atas agak mudah difahami Ia digunakan terutamanya untuk tatasusunan berdasarkan panjang ruang tatasusunan dimasukkan oleh pengguna, tetapi ia adalah khusus Apabila memohon tatasusunan, satu lagi ruang akan digunakan.

    tambah fungsi

    public boolean add(T o) {
        queue[tail] = o;
        // 循环使用数组
        int newtail = (tail + 1) % capacity;
        if (newtail == head)
            throw new IndexOutOfBoundsException("Queue full");
        tail = newtail;
        return true; // we did add something
    }

    Kod di atas agak mudah difahami bahawa

    boleh menggelungkan untuk menambah data Ini juga dinyatakan di atas dalam kod.

    ArrayQueuefungsi alih keluar

    public T remove(int i) {
        if (i != 0)
            throw new IllegalArgumentException("Can only remove head of queue");
        if (head == tail)
            throw new IndexOutOfBoundsException("Queue empty");
        T removed = queue[head];
        queue[head] = null;
        head = (head + 1) % capacity;
        return removed;
    }

    Seperti yang dapat dilihat daripada kod di atas, kita mesti lulus parameter 0 dalam fungsi

    , jika tidak pengecualian akan dilemparkan. Dalam fungsi ini, kami hanya akan memadamkan data pada kedudukan subskrip

    semasa, dan kemudian melakukan operasi kitaran menambah 1 pada nilai remove. Parameter fungsi headheadget

    public T get(int i) {
        int size = size();
        if (i < 0 || i >= size) {
            final String msg = "Index " + i + ", queue size " + size;
            throw new IndexOutOfBoundsException(msg);
        }
        int index = (head + i) % capacity;
        return queue[index];
    }

    menunjukkan bahawa data

    diperolehi getdata ke-1 bukan idata dalam kedudukan tatasusunan, tetapi Ia adalah data kedudukan i jauh dari i Mengetahui perkara ini, kod di atas mudah difahami. headifungsi ubah saiz

    public void resize(int newcapacity) {
        int size = size();
        if (newcapacity < size)
            throw new IndexOutOfBoundsException("Resizing would lose data");
        newcapacity++;
        if (newcapacity == this.capacity)
            return;
        T[] newqueue = newArray(newcapacity);
        for (int i = 0; i < size; i++)
            newqueue[i] = get(i);
        this.capacity = newcapacity;
        this.queue = newqueue;
        this.head = 0;
        this.tail = size;
    }

    Dalam fungsi

    , mula-mula memohon ruang tatasusunan dengan panjang baharu, kemudian salin data tatasusunan asal ke tatasusunan baharu satu demi satu bahawa dalam salinan ini Semasa proses,

    dan resize dikemas kini sekali lagi, dan ia bukan salinan tatasusunan mudah, kerana head mungkin tidak lagi 0 dalam operasi sebelumnya, jadi salinan baharu memerlukan kami mengambil ia daripada tatasusunan lama satu demi satu dan masukkan ke dalam tatasusunan baharu. Gambar berikut dapat melihat dengan jelas proses ini: tailhead

    Atas ialah kandungan terperinci Analisis kod sumber Java ArrayQueue.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

    Kenyataan:
    Artikel ini dikembalikan pada:yisu.com. Jika ada pelanggaran, sila hubungi admin@php.cn Padam