De combien de façons existe-t-il d’implémenter des files d’attente ?

Il existe trois façons d'implémenter des files d'attente, à savoir : 1. Implémenter la file d'attente basée sur une liste chaînée ; 2. Utiliser linkedList pour implémenter la file d'attente ; 3. Utiliser deux piles pour implémenter une file d'attente ;

Il existe 3 façons d'implémenter la file d'attente. Les méthodes d'implémentation sont :

1. basé sur la file d'attente de liste chaînée :

Ajoutez d'abord une classe de nœud comme élément de nœud dans la file d'attente

public class Node {//链表中的一个节点
Node next = null;
int data;
//构造函数，用于添加链表时候使用
public Node(int d) {
this.data = d;
};
}

Créez ensuite une nouvelle classe comme notre file d'attente, et implémentez l'entrée et la sortie de la file d'attente dans cette classe函数参数传入要入队的数据，根据传入的参数，新Ajoutez un nœud Node et déterminez si la file d'attente est vide dans la méthode de mise en file d'attente. Si la file d'attente est vide (head==tail), alors le nœud ajouté à la file d'attente est à la fois la tête et la queue de la file d'attente. Si la file d'attente n'est pas vide, pointez le pointeur suivant du nœud de queue vers l'élément, puis pointez le nœud de queue vers le nœud.

public void put(Integer data) {
Node newNode = new Node(data);//构造一个新节点
if(head == null && tail == null) {//队列为空
head = newNode;
tail = newNode;
}else {
tail.next = newNode;
tail = newNode;
}
}

② Opération de retrait de la file d'attente :

Si la file d'attente est vide, retournez vide. Si la file d'attente n'est pas vide, renvoyez le nœud principal de la file d'attente, puis réutilisez l'élément suivant du nœud principal comme nœud principal

public Integer pop() {
if(this.isEmpty()) {
return null;
}
int data = head.data;
head = head.next;
return data;
}

③ Il est très simple de juger la file d'attente vide et le longueur de la file d’attente. Collez simplement le code directement.

public int size() {
int count = 0;
Node tmp = head;
while(tmp != null) {
count++;
tmp = tmp.next;
}
return count;
}

④Implémentation détaillée du code :

package com.wp.datastruct;
 
/**
 * 利用链表来实现队列
 * */
public class MyQueue {
Node head = null;//队列头
Node tail = null;//队列尾
/**
* 入队操作：
* 若该队列尾空，则入队节点既是头结点也是尾节点
* 若队列不为空，则先用tail节点的next指针指向该节点
* 然后将tail节点指向该节点
* */
public void put(Integer data) {
Node newNode = new Node(data);//构造一个新节点
if(head == null && tail == null) {//队列为空
head = newNode;
tail = newNode;
}else {
tail.next = newNode;
tail = newNode;
}
}
/**
* 判断队列是否为空：当头结点等于尾节点的时候该队列就为空
* */
public boolean isEmpty() {
return head == tail;
}
/**
* 出队操作：
* 若队列为空，则返回null
* 否则，返回队列的头结点，并将head节点指向下一个
* */
public Integer pop() {
if(this.isEmpty()) {
return null;
}
int data = head.data;
head = head.next;
return data;
}
public int size() {
int count = 0;
Node tmp = head;
while(tmp != null) {
count++;
tmp = tmp.next;
}
return count;
}
 
}

2 Utilisez

pour implémenter la file d'attente

Cette méthode utilise la collection linkedList en Java Implement. une file d'attente et appelez les méthodes dans linkedList pour implémenter l'entrée et la sortie de la file d'attente, le jugement vide et d'autres opérations linkedListTout d'abord, créez une nouvelle classe comme notre file d'attente. Cette classe contient deux attributs, l'un est la taille : utilisé pour compter la file d'attente. longueur de la file d'attente, l'autre est un objet LinkedList,

représente notre file d'attente.

private LinkedList<E> list = new LinkedList<>();
private int size = 0;//用于统计队列的长度

① Opération de file d'attente :

Il devrait être que les opérations d'ajout et de suppression aient été implémentées dans la collection linkedList. Ici, il suffit simplement d'appeler la méthode pour implémenter les opérations liées à la file d'attente. , ce qui est très simple et facile à comprendre.

public synchronized void put(E data) {//保证线程安全，实现同步操作
list.add(data);
size++;
}

② Opération de retrait de la file d'attente :

public synchronized E pop() {
size--;
return list.removeFirst();//从头取出
}

③ Code détaillé :

public class MyQueue2 {
private LinkedList<E> list = new LinkedList<>();
private int size = 0;//用于统计队列的长度
public synchronized void put(E data) {//保证线程安全，实现同步操作
list.add(data);
size++;
}
public synchronized E pop() {
size--;
return list.removeFirst();//从头取出
}
public synchronized int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}

3. Utilisez deux piles pour implémenter une file d'attente.

Vous pouvez également utiliser deux piles implémentées pour implémenter une file d'attente (cette question pourra être posée lors de l'examen écrit). La méthode de mise en œuvre est la suivante :

Créer deux piles s1 et s2. Lorsque vous rejoignez la file d'attente, il est uniquement poussé sur la pile dans s1.

Il existe deux cas de retrait de la file d'attente : 1. Lorsque s2 n'est pas vide, l'élément supérieur de la pile est extrait en tant qu'élément de retrait de la file d'attente.

<.> 2. Lorsque S2 est égal à vide, faites d'abord apparaître tous les éléments de S1 dans S2, puis affichez l'élément supérieur de S2 en tant qu'élément de l'équipe.

①Entrez dans l'équipe :

public synchronized void put(E data) {//使用同步处理，保证线程安全
s1.push(data);
}

②Quitter l'équipe :

public synchronized E pop() {
if(!s2.isEmpty()) {
return s2.pop();
}else {
s2.push(s1.pop());
return s2.pop();
}
}

③ Implémentation détaillée du code :

package com.wp.datastruct;
 
import java.util.Stack;
 
/**
 * 利用两个栈来模拟队列操作
 * 入队操作就只是想栈s1中添加，
 * 出栈操作分为两部分：
 * 1.当s2中不为空的时候，就直接弹出s2中的栈顶数据
 * 2.当s2中为空的时候，就先把s1中的数据全部弹出到s2中然后将栈顶数据出栈
 * 
 * */
public class MyQueue3<E> {
Stack<E> s1 = new Stack<>();
Stack<E> s2 = new Stack<>();
public synchronized void put(E data) {//使用同步处理，保证线程安全
s1.push(data);
}
public synchronized E pop() {
if(!s2.isEmpty()) {
return s2.pop();
}else {
s2.push(s1.pop());
return s2.pop();
}
}
public synchronized boolean isEmpty() {
return s1.isEmpty() && s2.empty();
}
}

Tutoriel recommandé : 《

Tutoriel vidéo php

》

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!