データ構造とアルゴリズム-キュー
3772 ワード
チェーンテーブルを使用してキューを実現し、2つのポインタ、1つのテールポインタがエンキューを担当し、1つのヘッドポインタがエンキューを担当し、比較的簡単で、コードは以下の通りです.
ループキューは、配列を使用して実装されます.ここでは、主に式を使用して、キューがいっぱいであるかどうかを判断します(tail+1)%size=headですが、キューに空席があるため使用できません.コードは次のとおりです.
githubアドレス:https://github.com/freshbin/dataStructAndAlgo
package com.freshbin.dataStructAndAlgo.chapter06.mycode.queue;
/**
*
* @author freshbin
* @date 2020/4/14 17:32
*/
public class QueueBasedOnLinkedList {
private Node headNode;
private Node tailNode;
public QueueBasedOnLinkedList() {
}
public void enqueue(String value) {
System.out.println(" :" + value);
Node newNode = new Node(value);
if(tailNode == null) {
tailNode = newNode;
headNode = newNode;
return;
}
tailNode.next = newNode;
tailNode = tailNode.next;
}
public String dequeue() {
if(headNode == null) {
System.out.println(" ");
return null;
}
String returnData = headNode.data;
headNode = headNode.next;
System.out.println(" :" + returnData);
return returnData;
}
public static void main(String[] arg) {
String a = "a";
String b = "b";
QueueBasedOnLinkedList queueBasedOnLinkedList = new QueueBasedOnLinkedList();
queueBasedOnLinkedList.dequeue();
queueBasedOnLinkedList.enqueue(a);
queueBasedOnLinkedList.enqueue(b);
queueBasedOnLinkedList.dequeue();
queueBasedOnLinkedList.dequeue();
queueBasedOnLinkedList.dequeue();
}
public class Node {
private String data;
private Node next;
public Node() {
}
public Node(String value) {
this.data = value;
}
public String getData() {
return this.data;
}
public void setData(String data) {
this.data = data;
}
public Node getNext() {
return this.next;
}
public void setNext(Node next) {
this.next = next;
}
}
}
ループキューは、配列を使用して実装されます.ここでは、主に式を使用して、キューがいっぱいであるかどうかを判断します(tail+1)%size=headですが、キューに空席があるため使用できません.コードは次のとおりです.
package com.freshbin.dataStructAndAlgo.chapter06.mycode.queue;
/**
*
*
* :(tail+1)%size=head
* :head=tail
* tail ,head ,size
* @author freshbin
* @date 2020/4/14 17:51
*/
public class CircularQueue {
private Integer size;
private String[] dataArray;
private Integer head;
private Integer tail;
public CircularQueue() {
this(3);
}
public CircularQueue(int maxSize) {
this.size = maxSize+1;
dataArray = new String[this.size];
head = 0;
tail = 0;
}
public void enquue(String value) {
if((tail + 1) % size == head) {
System.out.println(" ");
return;
}
dataArray[tail] = value;
tail = (tail + 1) % size;
}
public String dequeue() {
if(tail == head) {
System.out.println(" !");
return null;
}
String returnValue = dataArray[head];
head = (head + 1) % size;
return returnValue;
}
public static void main(String[] arg) {
CircularQueue circularQueue = new CircularQueue();
circularQueue.dequeue();
for(int i = 0; i < 4; i++) {
circularQueue.enquue("queue" + i);
}
System.out.println(" :");
String dequeueData = circularQueue.dequeue();
while (dequeueData != null) {
System.out.print(dequeueData + " ");
dequeueData = circularQueue.dequeue();
}
}
}
githubアドレス:https://github.com/freshbin/dataStructAndAlgo