Stackの実装<LinkedList>

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

Node<T>クラス

ジェネリクスを使用して、複数の型に対応できるようにしておきます。

public class Node<T extends Comparable<T>> {

  
  private Node<T> next;
  private T data;
  
  public Node(T data) {
    this.data = data;
    this.next = null;
  }


  public T getData() {
    return data;
  }

  public void setData(T data) {
    this.data = data;
  }

  public Node<T> getNext() {
    return next;
  }

  public void setNext(Node<T> next) {
    this.next = next;
  }
}

Stackクラス

Stackクラスを作っていきます。

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

要素数を随時追跡できるようにするために、変数numを作成しておきます。

コンストラクタ

headをnullに初期化します。

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

追加メソッド

このメソッドが呼び出される度に、要素数を更新するようにします。

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

先端のノードを繋ぎかえることで、結果的にそれ以降のデータを奥にpushしていることになります。

削除メソッド

このメソッドが呼び出されるたびに、同じく要素数を更新するようにします。

public T pop(){
        if (num == 0){
            return null;
        }
        num --;
        Node<T> currNode = head;
        currNode = currNode.getNext();
        Node<T> tmp = currNode;
        head = currNode;
        return tmp.getData();
    }
public T getTop(){
        if (num>1){
            return head.getNext().getData();
        }
        return null;
    }

tmpで先端のノードを記録した後に、headを一つ分手繰り寄せます。

ついでに先端ノードの値を返すメソッドも用意しました。

ノードの可視化

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メソッド

１から１０まで順番にスタックに追加した後に、それを全て取り出してみます。

public static void main(String[] args) {
        Stack stack = new Stack<>();
        for (int i = 0;i < 10;i++){
            stack.push(i);
        }
        System.out.println(stack);
        while(stack.num>0){
            stack.pop();
            System.out.println(stack);
        } 
    }

実行結果

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