Un article pour vous présenter les piles et files d'attente Java

Cet article vous apporte des connaissances pertinentes sur java. Il organise principalement les problèmes liés aux piles et aux files d'attente, y compris la définition, l'application, la mise en œuvre et le fonctionnement des piles et des files d'attente. Examinons-les ensemble, j'espère que cela aidera tout le monde.

Apprentissage recommandé : "Tutoriel vidéo Java"

Avant d'apprendre les piles et les files d'attente, comprenez d'abord ce qu'est un tableau linéaire : enregistrer un seul élément du même type à la fois, et plusieurs éléments sont logiquement continus, tels que les tableaux, les listes chaînées, les chaînes, les piles et les files d'attente
Les piles et les files d'attente sont en fait des listes linéaires avec des opérations limitées. Qu'il s'agisse de tableaux ou de listes chaînées, elles peuvent être insérées et supprimées en tête et en queue, mais les piles et les files d'attente ne le peuvent que. Peut être inséré à une extrémité et supprimé à une extrémité

1. Pile

1 Définition

Les éléments ne peuvent être insérés qu'à une extrémité, et les éléments ne peuvent être supprimés qu'à cette extrémité (en haut de la pile). Considérez la pile comme une « tasse à eau ». Les éléments ne peuvent être ajoutés que par une extrémité, et les éléments ne peuvent être supprimés que par une seule section. De plus, l'eau qui entre en premier dans la tasse à eau se trouve au fond de la tasse. l'eau qui entre plus tard dans la tasse d'eau se trouve au sommet de la tasse. Lorsque vous versez de l'eau, l'eau du haut de la tasse est également versée, il en va de même pour les éléments qui sont poussés dans la pile. les premiers sont au bas de la pile, et les éléments qui sont poussés dans la pile plus tard sont en haut de la pile. Par conséquent, les éléments qui sont poussés dans la pile en premier sont retirés en dernier, et les éléments qui y sont poussés. les derniers de la pile sont retirés en premier C'est aussi la caractéristique de la pile : "premier entré, dernier sorti, dernier entré premier" "Last In First Out (LIFO), les éléments retirés et les éléments ajoutés ne peuvent être que sur le dessus de la pile. empiler.
Mettez 1 2 3 4 5 dans la pile à la fois

2. Application Stack

1. L'opération d'annulation (annulation) omniprésente

Après avoir tapé quelque chose de mal dans n'importe quel éditeur, utilisez Ctrl + z pour revenir à l'entrée. contenu ;
Cliquer sur l'opération de retour dans n'importe quel navigateur

est une application de cette structure de pile
1. Utilisez l'éditeur pour utiliser l'opération d'annulation et poussez le contenu dans la pile une fois saisi, si vous saisissez à nouveau, appuyez à nouveau dans la pile. Si vous trouvez une erreur d'entrée, utilisez l'opération d'annulation pour placer le contenu de l'erreur en haut de la pile actuelle. Le contenu en haut de la pile actuelle est ensuite le dernier contenu d'entrée.
2. La navigation sur le Web est en fait basée sur le même principe, tout comme l'ouverture de Baidu -> Ouvrir csdn -> Ouvrir le centre de création, qui utilise également la structure de pile. Poussez d'abord la page Web Baidu dans la pile, puis poussez la. page Web csdn dans la pile. Ensuite, la page Web du centre de création est poussée dans la pile. Si vous souhaitez revenir à la page d'accueil csdn, appuyez sur la flèche arrière pour afficher la page Web du centre de création actuellement en haut de la pile et. retirez la page d'accueil du csdn.

2. Pile du système d'exploitation

Pendant l'exécution du programme, la fonction B est appelée à partir de la fonction A et la fonction C est appelée à partir de la fonction B. Lorsque l'appel se termine et revient à l'exécution, comment savoir où continuer l'exécution ? Il y a aussi une pile derrière cette structure

3. Implémentation de la pile

Pile implémentée basée sur une liste chaînée
Pile implémentée basée sur un tableau – pile séquentielle (plus couramment utilisée)
Définir une pile implémentée basée sur un tableau dynamique

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

4. Opération de pile

1. Ajouter un élément à la pile
ne peut être ajouté qu'en haut de la pile

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

2. Afficher actuellement un élément du haut de la pile

/**
     * 弹出当前栈顶元素,返回栈顶元素的值
     * @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;
    }

3. élément supérieur actuel de la pile, mais ne le faites pas apparaître

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

2. File d'attente

1 Définition

File d'attente : structure de données premier entré, premier sorti (FIFO) i. la fin de la file d'attente et ne peut être retiré de la file d'attente qu'à partir de la tête de la file d'attente. L'ordre de sortie de la file d'attente et l'ordre d'entrée des éléments sont cohérents
Mettez 1 2 3 4 5 dans la file d'attente dans l'ordre

2. Application de file d'attente.

Dans la vraie vie, diverses opérations de "file d'attente"

3. Implémentation de la file d'attente

File d'attente basée sur l'implémentation d'un tableau – File d'attente séquentielle
Une file d'attente implémentée basée sur une liste chaînée – file d'attente chaînée
L'opération de retrait de la file d'attente ne peut être effectuée qu'en tête de la file d'attente. Si une file d'attente implémentée par un tableau est utilisée, chaque fois qu'un élément est retiré de la file d'attente, tous les éléments restants doivent être avancés. À ce moment, la file d'attente implémentée par la liste chaînée est plus adaptée à la structure de la file d'attente. . Pour supprimer un élément, il vous suffit de supprimer le nœud principal. Pour ajouter un élément, ajoutez

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

à la fin de la liste chaînée. Pour les piles, il existe de nombreuses sous-classes d'implémentation de file d'attente, telles que
File d'attente FIFO
Double. -file d'attente terminée
File d'attente circulaire
File d'attente prioritaire
Quelle que soit la file d'attente qui doit être implémentée

4 Queue FIFO

1 Définissez une file d'attente FIFO

// An highlighted blockvar foo = 'bar';

2 Ajoutez un élément à la file d'attente

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>

3. depuis la tête de la file d'attente actuelle

 public E poll() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot poll!");
        }
        //头删
        E val = head.val;
        Node<e> node = head;
        head = head.next;
        node.next = node = null;
        size--;
        return val;
    }</e>

4. Afficher l'élément de tête de la file d'attente actuelle

.

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!