Queueの実装<LinkedList>

今回はLinkedListを使用して一からQueueを実装していきます。

Queueクラス

public class Queue<T extends Comparable<T>> {
    Node<T> head;
    int num;
    ...
}

コンストラクタ

public Queue(){
        head = new Node<T>(null);
        num = 0;
    }

追加メソッド

追加する際はStackと同じ方針にします。

public void add(T element){
        num ++;
        Node<T> newNode = new Node<T>(element);
        Node<T> currNode = head;
        currNode = currNode.getNext();
        newNode.setNext(currNode);
        head.setNext(newNode);
    }

削除メソッド

queueでは先に入れたものから取り出すので、一番後ろの要素まで手繰り寄せてからそれを削除します。

もし、メンバ変数にtailノードを追跡するものがあればO(1)の計算量で行えますが、シンプルにしたいので使いません。

public T remove(){
        if (num == 0){
            return null;
        }
        num--;
        Node<T> currNode = head;
        while(currNode.getNext().getNext() != null){
            currNode = currNode.getNext();
        }
        Node<T> temp = currNode.getNext();
        currNode.setNext(null);
        return temp.getData();
    }

toString()メソッド

public String toString(){
        String result = "-|";
        Node<T> currNode = head;
        int i = 0;
        while(currNode.getNext() != null){
            currNode = currNode.getNext();
            if (i < num -1){
                result += currNode.getData() + "|-|";
            }else{
                result += currNode.getData() + "|";
            }
            i++;
        }
        return result;
    }

mainクラス

Stackと同様に１から１０までの数を格納後、要素数がゼロになるまで取り出していきます。

 public static void main(String[] args) {
        Queue queue = new Queue<>();
        for (int i = 0;i < 10;i++){
            queue.add(i);
        }
        System.out.println(queue);
        while(queue.num>0){
            queue.remove();
            System.out.println(queue);  
        }
    }

実行結果

-|9|-|8|-|7|-|6|-|5|-|4|-|3|-|2|-|1|-|0|
-|9|-|8|-|7|-|6|-|5|-|4|-|3|-|2|-|1|
-|9|-|8|-|7|-|6|-|5|-|4|-|3|-|2|
-|9|-|8|-|7|-|6|-|5|-|4|-|3|
-|9|-|8|-|7|-|6|-|5|-|4|
-|9|-|8|-|7|-|6|-|5|
-|9|-|8|-|7|-|6|
-|9|-|8|-|7|
-|9|-|8|
-|9|