キューを実装する方法は何通りありますか?

キューを実装するには 3 つの方法があります: 1. リンク リストに基づいてキューを実装する; 2. linkedList を使用してキューを実装する; 3. 2 つのスタックを使用してキューを実装する。

キューを実装するには 3 つの方法があります。実装方法は次のとおりです:

1. 実装ベースリンクされたリストのキュー:

まず、ノード要素としてノード クラスをキューに追加します

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

次に、新しいクラスをキューとして作成し、キュー エントリを実装して終了します。このクラス チームの長さと判定、キューのキューが空である ノード Node を追加し、enqueue メソッドでキューが空かどうかを判定する キューが空 (head==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 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;
}

④詳細なコード実装:

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.

linkedList

を使用してキューを実装します

このメソッドは Java で使用されますlinkedList コレクションを使用してキューを実装し、linkedList 内のメソッドを呼び出してキューの出入り、空の判定、その他の操作を実装します。最初に、2 つの属性を含む新しいクラスをキューとして作成します。 1 つはサイズです。キューの長さをカウントするために使用され、もう 1 つは LinkedList オブジェクトです。

はキューを表します。

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

① キュー操作:

追加操作と削除操作が linkedList コレクションに実装されているはずです。ここでは、キュー関連の操作を実装するメソッドを呼び出すだけです。 、非常にシンプルで理解しやすいです。

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

② デキュー操作:

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

③ 詳細コード:

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. 2 つのスタックを使用してキューを実装します。

実装された 2 つのスタックを使用してキューを実装することもできます (この質問は書面面接で尋ねられる場合があります)。 実装方法は次のとおりです。

2 つのスタック s1 と s2 を作成します。キューに参加するときは、スタックの s1 にプッシュされるだけです。

デキューには 2 つのケースがあります。 1. s2 が空でない場合、スタックの最上位要素がデキュー要素としてポップされます。

2. S2 が空の場合、まず S1 の要素を S2 にポップし、次に S2 の最上位の要素をチームの要素としてポップアップします。

① チームへの参加:

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

③. 詳細なコード実装:

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

推奨チュートリアル: "

php ビデオ チュートリアル

"

以上がキューを実装する方法は何通りありますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。