Wie viele Möglichkeiten gibt es, Warteschlangen zu implementieren?

Es gibt drei Möglichkeiten, Warteschlangen zu implementieren: 1. Implementieren Sie die Warteschlange basierend auf einer verknüpften Liste. 2. Verwenden Sie LinkedIn, um die Warteschlange zu implementieren. 3. Verwenden Sie zwei Stapel, um eine Warteschlange zu implementieren.

Es gibt drei Möglichkeiten, die Warteschlange zu implementieren:

1 basierend auf der verknüpften Liste Warteschlange:

Fügen Sie zuerst eine Knotenklasse als Knotenelement in der Warteschlange hinzu

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

Erstellen Sie dann eine neue Klasse als unsere Warteschlange und implementieren Sie den Warteschlangenein- und -ausgang in dieser Klasse队以及求队列的长度和判断队列是否为空等方法

①入队操作:

             首先通过函数参数传入要入队的数据,根据传入的Fügen Sie in der Enqueue-Methode einen Knoten hinzu und bestimmen Sie, ob die Warteschlange leer ist (Kopf==Ende), dann ist der zur Warteschlange hinzugefügte Knoten sowohl der Kopf als auch das Ende der Warteschlange. Wenn die Warteschlange nicht leer ist, zeigen Sie mit dem nächsten Zeiger des Endknotens auf das Element und dann mit dem Endknoten auf den Knoten.

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;
}
}

② Vorgang aus der Warteschlange entfernen:

Wenn die Warteschlange leer ist, geben Sie sie leer zurück. Wenn die Warteschlange nicht leer ist, geben Sie den Kopfknoten der Warteschlange zurück und verwenden Sie dann das nächste Element des Kopfknotens erneut als Kopfknoten

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

③ Es ist sehr einfach, die leere Warteschlange und die zu beurteilen Länge der Warteschlange. Fügen Sie einfach den Code ein.

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

④Detaillierte Code-Implementierung:

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. Verwenden Sie , um die Warteschlange zu implementieren. linkedList

Diese Methode verwendet die LinkedInList-Sammlung in Java Erstellen Sie eine Warteschlange und rufen Sie die Methoden in linkedList auf, um den Ein- und Ausgang der Warteschlange, die leere Beurteilung und andere Operationen zu implementieren.

Erstellen Sie zunächst eine neue Klasse als unsere Warteschlange. Diese Klasse enthält zwei Attribute, eines ist size: Wird zum Zählen verwendet Länge der Warteschlange, das andere ist ein LinkedList-Objekt,

repräsentiert unsere Warteschlange.

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

① Warteschlangenoperation:

Es sollte sein, dass die Add- und Löschoperationen in der LinkedInList-Sammlung implementiert wurden. Hier müssen wir nur die Methode aufrufen, um die warteschlangenbezogenen Operationen zu implementieren , was sehr einfach und leicht zu verstehen ist.

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

② Vorgang aus der Warteschlange:

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

③ Detaillierter Code:

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. Verwenden Sie zwei Stapel, um eine Warteschlange zu implementieren.

Sie können auch zwei implementierte Stacks verwenden, um eine Warteschlange zu implementieren (diese Frage kann während des schriftlichen Tests gestellt werden).

Die Implementierungsmethode ist:

Erstellen Sie zwei Stapel s1 und s2. Beim Beitritt zur Warteschlange wird es nur in s1 auf den Stapel geschoben.

Es gibt zwei Fälle des Entfernens aus der Warteschlange: 1. Wenn s2 nicht leer ist, wird das oberste Element des Stapels als Element zum Entfernen aus der Warteschlange entnommen.

<.> 2. Wenn S2 gleich leer ist, werden zuerst alle Elemente in S1 in S2 eingefügt und dann das oberste Element aus S2 als Element des Teams angezeigt.

①Betreten Sie das Team:

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

②Verlassen Sie das Team:

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

③. Detaillierte Code-Implementierung:

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();
}
}

Empfohlenes Tutorial: 《

PHP-Video-Tutorial

》

Das obige ist der detaillierte Inhalt vonWie viele Möglichkeiten gibt es, Warteschlangen zu implementieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!