Artikel untuk memperkenalkan anda kepada susunan dan baris gilir Java

Artikel ini membawa anda pengetahuan yang berkaitan tentang java, yang terutamanya mengatur isu yang berkaitan dengan tindanan dan baris gilir, termasuk definisi, aplikasi, pelaksanaan dan pengendalian tindanan dan baris gilir, dsb. , mari kita lihat bersama-sama, saya harap ia akan membantu semua orang.

Kajian yang disyorkan: "tutorial video java"

Sebelum mempelajari tindanan dan baris gilir, fahami dahulu apa itu jadual linear: Simpan satu elemen daripada jenis yang sama pada satu masa dan berbilang elemen secara logiknya berterusan, seperti tatasusunan, senarai terpaut, rentetan, tindanan dan baris gilir
Tindanan dan baris gilir sebenarnya adalah senarai linear dengan operasi terhad, sama ada tatasusunan atau terpaut senarai, kedua-dua Memasukkan dan memadam di kepala juga boleh dilakukan di bahagian ekor, tetapi tindanan dan baris gilir hanya boleh dimasukkan pada satu hujung dan dipadamkan pada satu hujung

1. Tindanan

1. Definisi

Anda hanya boleh memasukkan elemen pada satu hujung, dan anda hanya boleh memadamkan elemen di hujung ini (atas tindanan Anda boleh menganggap timbunan sebagai "cawan air". dari satu hujung, dan anda hanya boleh memadamkan elemen dari satu bahagian Selain itu, pertama Air yang masuk ke dalam cawan air adalah di bahagian bawah cawan, dan air yang masuk ke dalam cawan air kemudiannya adalah di bahagian atas cawan anda menuangkan air keluar, air dari bahagian atas cawan juga dicurahkan. Begitu juga dengan timbunan Unsur-unsur yang ditolak ke dalam timbunan adalah di bahagian bawah timbunan, dan unsur-unsur yang ditolak ke dalam timbunan. timbunan kemudian adalah Ia berada di bahagian atas timbunan, jadi unsur-unsur yang ditolak ke dalam timbunan dahulu dikeluarkan terakhir, dan unsur-unsur yang ditolak ke dalam timbunan terakhir dikeluarkan dahulu. Ini juga merupakan ciri-ciri timbunan Bahagian atas timbunan.
Masukkan 1 2 3 4 5 ke dalam tindanan sekaligus

2. Aplikasi tindanan

1 >Selepas menaip sesuatu yang salah dalam mana-mana editor, gunakan Ctrl z untuk kembali ke kandungan yang dimasukkan

Klik operasi belakang dalam mana-mana pelayar

Semua Aplikasi struktur tindanan ini 1 . Gunakan editor untuk menggunakan operasi buat asal Setelah anda memasukkan, kandungan ditolak ke dalam tindanan kandungan semasa. Jika kandungan ralat di bahagian atas tindanan muncul, kandungan semasa di bahagian atas tindanan akan menjadi kandungan input terakhir.
2. Menyemak imbas web sebenarnya berdasarkan prinsip yang sama, seperti membuka Baidu -> Buka csdn -> kemudian tolak halaman web csdn ke dalam tindanan , dan kemudian tolak halaman web pusat penciptaan ke dalam tindanan Jika anda ingin kembali ke halaman utama csdn, tekan anak panah belakang untuk muncul halaman web pusat penciptaan yang kini berada di bahagian atas. timbunan dan keluarkan halaman utama csdn.

2. Timbunan sistem pengendalian

Semasa pelaksanaan semula program, fungsi B dipanggil daripada fungsi A, dan fungsi C dipanggil daripada fungsi B. Apabila panggilan tamat dan kembali ke pelaksanaan, bagaimana anda tahu di mana hendak bermula? Teruskan untuk melaksanakan, di belakangnya adalah struktur tindanan

3 Pelaksanaan tindanan

Timbunan dilaksanakan berdasarkan senarai terpaut - tindanan berantai

Timbunan dilaksanakan. berdasarkan tatasusunan – susunan berjujukan (gunakan yang agak Banyak)

Tentukan tindanan berdasarkan tatasusunan dinamik

4 Operasi tindanan

//基于动态数组实现的顺序栈public class MyStack<e> {
    //记录当前栈的元素个数
    private int size;
    //实际存储数据的动态数组，此时在栈中只能在数组的尾部添加和删除元素
    private List<e> data = new ArrayList();
    }</e></e>

1 🎜> Hanya boleh ditambah di bahagian atas tindanan

2 sedang memaparkan elemen dari bahagian atas tindanan

 /**
     * 向当前栈中添加元素 -- >压栈操作
     * @param val
     */
    public void push(E val){
        data.add(val);
        size++;
    }

3 tindanan, tetapi tidak memunculkannya

/**
     * 弹出当前栈顶元素,返回栈顶元素的值
     * @return
     */
    public E pop(){
        if (isEmpty()){
            //栈为空无法弹出
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        //在数组末尾删除元素
        E val = data.get(size - 1);
        data.remove(size - 1);
        size --;
        return val;
    }

2. Baris gilir

/**
     * 查看当前栈顶元素值，不弹出该元素
     * @return
     */
    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek!");
        }
        return data.get(size - 1);
    }

1 Definisi

Baris gilir: Struktur data masuk dahulu (FIFO) i. Elemen hanya boleh ditambah pada baris gilir dari penghujung baris gilir, dan hanya boleh dialih gilir dari permulaan baris gilir Elemen Urutan nyah gilir dan susunan memasuki baris gilir adalah konsisten

Enqueue 1 2 3 4. 5 mengikut urutan

2. Aplikasi baris gilir

Dalam kehidupan sebenar, pelbagai Pelbagai operasi "beratur"

3. Pelaksanaan giliran

Pelaksanaan baris gilir berasaskan tatasusunan – baris gilir berurutan

Pelaksanaan baris gilir berasaskan senarai terpaut – baris gilir berantai

Operasi dequeue Ia hanya boleh dilakukan di kepala baris gilir jika baris gilir dilaksanakan menggunakan tatasusunan, setiap kali satu elemen dinyah gilir, semua elemen yang tinggal perlu digerakkan ke hadapan satu unit Pada masa ini, baris gilir yang dilaksanakan menggunakan senarai terpaut lebih sesuai untuk struktur Padam Elemen hanya perlu memadamkan nod kepala, menambah elemen

di penghujung senarai terpaut Untuk tindanan, terdapat banyak subkelas pelaksanaan baris gilir, seperti

gilir FIFO

public interface Queue<e> {
    //入队操作
    void offer(E val);
    //出队操作
    E poll();
    //查看队首元素
    E peek();
    boolean isEmpty();}</e>

gilir dua hujung

Gilir pekeliling
Barisan keutamaan
Tidak kira baris gilir mana yang dilaksanakan

4 baris gilir FIFO

1 Tentukan baris gilir FIFO

2

// An highlighted blockvar foo = 'bar';

3. Nyah gilir elemen daripada kepala baris gilir semasa

public void offer(E val) {
        Node<e> node = new Node(val);
        if (head == null){
            head = tail = node;
        }else{
            //链表的尾插
            tail.next = node;
            tail = node;
        }
        size++;
    }</e>

4

public E peek() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }

5.循环队列

1.定义：基本上都是使用固定长度的数组来实现，数组在实现队时，若从数组头部删除元素需要频繁的移动后面的元素，效率比较低；出队和入队操作，使用两个引用，一个head，一个tail,添加元素在数组的尾部添加，删除元素只需要移动head引用指向的地址即可（逻辑删除）
2.应用：操作系统的生产消费者模型，MySQL数据库的InnoDB存储引擎的redo日志
3.循环队列就是使用长度固定的数组来实现，数组头部就是队首（head），数组的尾部就是队尾（tail），数组[head…tail)时循环队列的有效元素
head永远指向循环队列的第一个元素
tai永远指向循环队列有效元素的后一个位置

此时循环队列的有效元素就为7 9 1两个元素
循环队列出队一个元素，就只用让head引用向后移动一个位置

此时循环队列的有效元素就只有9 和 1 两个元素了
再出队一个元素，但此时head引用已经走到末尾了，所谓循环队列就是当head或者tail引用走到数组末尾时，再向后移动就是返回数组头部的操作，循环队列最大好处就是进行元素的删除的时候不需要进行数据的搬移操作，当有新的元素添加到队列中就会覆盖掉原来的元素，就只需要将tail索引位置覆盖上新的元素，再让tail再向后移动

当队列为空时,head == tail

当队列已“满”时，head == tail

循环队列需要注意的关键点
1.因此当head 和 tail相等时，没法区分此时循环队列已满，还是为空，因此在循环队列中，若(tail + 1) % n == head就认为循环队列已满

此时循环队列就已经满了，在循环队列中就会浪费一个空间，判断队列是否已满
2.head和tail的移动不能简单的 + 1，使用取模操作，取数组长度
tail = (tail + 1) % n
head = (head + 1) % n
对数组长度取模的本质：
当head和tai走到数组最后一个索引位置时，下一次要返回数组头部，就必须用 + 1对数组长度取模
3.head == tail时，认为队列为空

6.循环队列的操作

1.定义一个循环队列

//基于整形的循环队列public class LoopQueue implements Queue<integer> {
    //定长数组
    private Integer[] data;
    //指向队首元素
    int head;
    //指向队尾元素的下一个元素
    int tail;
    public LoopQueue(int size){
        data = new Integer[size + 1];
    }}</integer>

2.向循环队列中添加一个元素

@Override    public void offer(Integer val) {
       if (isFull()){
           throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer");
       }
       data[tail] = val;
       tail = (tail + 1) % data.length;
    }

3.从循环队列中出队一个元素

 @Override    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot poll!");
        }
        Integer val = data[head];
        head = (head + 1) % data.length;
        return val;
    }

4.查看当前循环队列队首元素

 @Override    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot peek!");
        }
        return data[head];
    }

5.判断当前循环队列是否为空

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

6.判断当前循环队列是否已满

 public boolean isFull(){
        return (tail + 1) % data.length == head;
    }

7.toString方法

public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        //最后一个有效元素的索引
        int lsatIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = head; i != tail;) {
            sb.append(data[i]);
            if (i != lsatIndex){
                sb.append(", ");
            }
            i = (i + 1) % data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }

---

7.双端队列

双端队列：Deque是Queue的子接口，这个队列既可以尾插，头出；也可以头插，尾出

双端队列的一个常用子类就是LinkedList，不管使用栈还是队列，都可以统一使用双端队列接口
1.现在需要一个栈

2.现在需要一个队列

推荐学习：《java视频教程》

Atas ialah kandungan terperinci Artikel untuk memperkenalkan anda kepada susunan dan baris gilir Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!