Bagaimana untuk melaksanakan baris gilir pekeliling di java

1. Apakah masalah beratur biasa?

Seperti yang kita semua tahu, baris gilir mempunyai beberapa atribut penting:

• belakang: menunjuk ke ekor baris gilir, iaitu kedudukan elemen terakhir , dan nilai awal ialah -1

• depan: menunjuk ke kedudukan sebelumnya bagi kepala baris gilir, dan nilai awal juga ialah -1

• kapasiti: kapasiti barisan

Belakang dan hadapan barisan kosong kedua-duanya sama dengan -1 Apabila memasuki barisan, bahagian hadapan tidak bergerak dan belakang++ . Apabila rear == capacity - 1, baris gilir penuh; Ia kelihatan sempurna, tetapi sebenarnya ada sesuatu yang tidak kena dengannya. Jika baris gilir front == rear mempunyai tiga elemen dalam baris gilir, kali ini capacity = 3, dan kemudian ketiga-tiga elemen dinyah gilir, kali ini front = -1; rear = 2. Pada masa ini, baris gilir jelas kosong, tetapi tiada lagi elemen boleh ditambah pada baris gilir, kerana ia memenuhi front = 2, rear = 2, yang bermaksud bahawa baris gilir adalah satu kali dan tidak boleh digunakan lagi Walaupun ia kosong, ia tidak boleh ditambah lagi Beratur, mengakibatkan pembaziran ruang, jadi baris gilir bulat muncul. rear = capacity - 1

2. Idea pelaksanaan baris gilir:

Beberapa atribut penting dalam baris gilir:

• belakang: menunjuk ke arah baris gilir Kedudukan selepas ekor, nilai awal ialah 0

• depan: menunjuk ke kepala baris gilir, iaitu kedudukan elemen pertama, nilai awal ialah 0

• kapasiti: kapasiti baris gilir

Berikut ialah beberapa algoritma untuk baris gilir cincin:

• Apabila baris gilir kosong:

  front == rear

• Apabila barisan penuh:

  (rear + 1) % capacity == front

• Dapatkan bilangan elemen baris gilir:

  (rear + capacity - front) % capacity

• Apabila menyertai pasukan:

  rear = (rear + 1) % capacity

• Semasa operasi nyah gilir:

  front = (front + 1) % capacity;

Menentukan sama ada baris gilir penuh adalah bahagian yang paling penting dan sukar difahami dalam baris gilir. Jika terdapat baris gilir

, operasi enqueue adalah seperti berikut: capacity = 3

• Elemen pertama dimasukkan ke dalam baris gilir:  

  , kerana front = 0, jadi elemen boleh ditambah pada baris gilir Selepas elemen itu ditambahkan pada pasukan  (rear + 1) % capacity = 1 % 3 != front;rear = 1

• Elemen kedua dimasukkan ke dalam baris gilir:  

  , kerana front = 0, jadi elemen boleh ditambah pada baris gilir Selepas elemen itu ditambahkan pada pasukan  (rear + 1) % capacity = 2 % 3 != front;rear = 2

• Elemen ketiga ditambahkan pada baris gilir:  

  , kerana front = 0, jadi elemen itu tidak boleh ditambah pada baris gilir dan baris gilir penuh; saya bahawa barisan penuh? Ya, algoritma ini untuk menentukan sama ada baris gilir penuh memerlukan pengorbanan ruang dalam tatasusunan. (rear + 1) % capacity = 3 % 3 == front

  Sekarang laksanakan operasi dequeue:

Elemen pertama dinyah gilir:  

,  

,    

.

• front = 1rear = 2Boleh didapati bahawa apabila sesuatu elemen dinyah gilir, ia memenuhi syarat untuk menyertai baris gilir, jadi ruang tatasusunan boleh digunakan semula. (rear + 1) % capacity = 3 % 3 = 0 != front

3. Amalan kod:

<code>public class CircleQueue<E> {<br>    private int capacity;<br>    private int front;<br>    private int rear;<br>    private Object[] arr;<br><br>    public CircleQueue(int capacity){<br>        this.capacity = capacity;<br>        this.arr = new Object[capacity];<br>        this.front = 0;<br>        this.rear = 0;<br>    }<br><br>    public boolean isFull(){<br>        return (rear + 1) % capacity == front;<br>    }<br><br>    public boolean isEmpty(){<br>        return rear == front;<br>    }<br><br>    public void addQueue(E e){<br>        if (isFull()){<br>            throw new RuntimeException("队列已满，入队失败");<br>        }<br>        arr[rear] = e;<br>        // rear指针后移<br>        rear = (rear + 1) % capacity;<br>    }<br><br>    public E getQueue(){<br>        if (isEmpty()){<br>            throw new RuntimeException("队列为空，出队失败");<br>        }<br>        E val = (E) arr[front];<br>        front = (front + 1) % capacity;<br>        return val;<br>    }<br><br><br>    public int getSize(){<br>        return (rear + capacity - front) % capacity;<br>    }<br><br>    // 遍历<br>    public void showQueue(){<br>        if (isEmpty()){<br>            return;<br>        }<br>        for (int i = front; i < front + getSize(); i++) {<br/>            System.out.printf("arr[%d]=%d\n", i%capacity, arr[i%capacity]);<br/>        }<br/>    }<br/><br/>    public static void main(String[] args){<br/>        CircleQueue<Integer> queue = new CircleQueue<>(3);<br>        queue.addQueue(1);<br>        queue.addQueue(2);<br>        queue.showQueue();<br>        //queue.addQueue(3);<br>        System.out.println(queue.getSize());<br>        System.out.println(queue.getQueue());;<br>        queue.addQueue(3);<br>        queue.showQueue();<br>    }<br>}</code>

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan baris gilir pekeliling di java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!