Ein Artikel, der Sie in Java-Stacks und -Warteschlangen einführt

Dieser Artikel vermittelt Ihnen relevantes Wissen über Java. Er organisiert hauptsächlich Probleme im Zusammenhang mit Stacks und Warteschlangen, einschließlich der Definition, Anwendung, Implementierung und Bedienung von Stacks und Warteschlangen. Ich hoffe, es hilft allen.

Empfohlene Studie: „Java-Video-Tutorial“

Bevor Sie Stapel und Warteschlangen lernen, verstehen Sie zunächst, was eine lineare Tabelle ist: Speichern Sie jeweils ein einzelnes Element desselben Typs, und mehrere Elemente sind logisch fortlaufend. wie Arrays, verknüpfte Listen, Zeichenfolgen, Stapel und Warteschlangen
Stapel und Warteschlangen sind eigentlich lineare Listen mit begrenzten Operationen. Ob Arrays oder verknüpfte Listen, sie können am Kopf oder am Ende eingefügt und gelöscht werden, Stapel und Warteschlangen jedoch nur an einem Ende eingefügt und an einem Ende gelöscht werden

1. Stapel

1. Elemente können nur an einem Ende eingefügt werden und Elemente können nur an diesem Ende (oben im Stapel) gelöscht werden des Stapels als „Wasserbecher“. Elemente können nur an einem Ende hinzugefügt und Elemente nur aus einem Abschnitt gelöscht werden. Darüber hinaus befindet sich das Wasser, das zuerst in den Wasserbecher gelangt, am Boden des Bechers Das, was später in den Wasserbecher gelangt, befindet sich oben im Becher. Dasselbe gilt für die Elemente, die zuerst in den Stapel geschoben werden befinden sich unten im Stapel und die Elemente, die später in den Stapel geschoben werden, befinden sich oben im Stapel. Daher werden die Elemente, die zuerst in den Stapel geschoben werden, zuletzt herausgenommen und die Elemente, die in den Stapel geschoben werden Stapelletzte werden zuerst herausgenommen. Dies ist auch das Merkmal des Stapels: „Zuerst rein, zuletzt raus, zuletzt rein.“ „Zuletzt rein, zuerst raus“ (LIFO), entnommene Elemente und hinzugefügte Elemente können nur oben auf dem Stapel liegen .

Legen Sie 1 2 3 4 5 auf einmal in den Stapel

2. Stapelanwendung

1. Nachdem Sie in einem beliebigen Editor etwas Falsches eingegeben haben, kehren Sie mit Strg + Z zum eingegebenen Wert zurück Inhalt;

Das Klicken auf den Zurück-Vorgang in einem beliebigen Browser

ist eine Anwendung dieser Struktur des Stapels
1. Verwenden Sie den Editor, um den Rückgängig-Vorgang zu verwenden, und verschieben Sie den Inhalt nach der Eingabe in den Stapel. Wenn Sie ihn erneut eingeben, drücken Sie Wenn Sie einen Eingabefehler finden, verwenden Sie die Rückgängig-Operation, um den fehlerhaften Inhalt oben auf dem aktuellen Stapel abzulegen. Dann ist der Inhalt oben auf dem aktuellen Stapel der zuletzt eingegebene Inhalt.
2. Das Surfen im Internet basiert tatsächlich auf dem gleichen Prinzip, genau wie das Öffnen von Baidu -> Öffnen Sie csdn -> Öffnen Sie das Erstellungszentrum, das ebenfalls die Stapelstruktur verwendet. Schieben Sie zuerst die Baidu-Webseite in den Stapel und dann csdn-Webseite in den Stapel verschieben. Wenn Sie zur csdn-Startseite zurückkehren möchten, drücken Sie den Zurück-Pfeil, um die aktuell oben im Stapel befindliche Webseite anzuzeigen Nehmen Sie die csdn-Homepage heraus.
2. Betriebssystemstapel

Während der Ausführung des Programms wird Funktion B von Funktion A und Funktion C von Funktion B aufgerufen. Wenn der Aufruf endet und zur Ausführung zurückkehrt, woher wissen Sie, wo die Ausführung fortgesetzt werden soll? ? Dahinter steckt auch ein Stapel. Diese Struktur.

Stapelimplementierung basierend auf einer verknüpften Liste – verketteter Stapel.

Stapel implementiert basierend auf einem Array – sequenzieller Stapel (häufiger verwendet).

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

4. Ein Element zum Stapel hinzufügen

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

3 Aktuelles oberstes Element des Stapels, aber nicht öffnen

/**
     * 弹出当前栈顶元素,返回栈顶元素的值
     * @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. Warteschlange
Warteschlange: First-In-First-Out (FIFO)-Datenstruktur i am Ende der Warteschlange und kann nur vom Kopf der Warteschlange entfernt werden. Die Reihenfolge beim Entfernen und Eintreten der Elemente wird konsistent beibehalten.

1 2 3 4 5 in die Warteschlange einreihen

2. Warteschlangenanwendung

Im wirklichen Leben verschiedene „Warteschlangen“-Operationen

3. Warteschlangenimplementierung

Warteschlange basierend auf Array-Implementierung – sequentielle Warteschlange

Eine Warteschlange basierend auf verknüpfter Liste – verkettete Warteschlange

Die Dequeue-Operation kann nur an der Spitze von ausgeführt werden Wenn eine durch ein Array implementierte Warteschlange verwendet wird, müssen jedes Mal, wenn ein Element aus der Warteschlange entfernt wird, alle verbleibenden Elemente nach vorne verschoben werden. Zu diesem Zeitpunkt ist die durch die verknüpfte Liste implementierte Warteschlange besser für die Warteschlangenstruktur geeignet . Um ein Element zu löschen, müssen Sie nur den Kopfknoten löschen. Fügen Sie am Ende der verknüpften Liste

rrree
hinzu. Für Stapel gibt es viele Unterklassen der Warteschlangenimplementierung, z. B.
FIFO-WarteschlangeDouble -endete Warteschlange

Zirkuläre Warteschlange

Egal welche Warteschlange implementiert werden muss

1. Definieren Sie eine FIFO-Warteschlange

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

3 vom Kopf der aktuellen Warteschlange

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

4. Zeigen Sie das Kopfelement der aktuellen Warteschlange an

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视频教程》

Das obige ist der detaillierte Inhalt vonEin Artikel, der Sie in Java-Stacks und -Warteschlangen einführt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!