キューを実装するには 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 MyQueue2.{ 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; } }
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 サイトの他の関連記事を参照してください。