Javaでスタックとキューを実装 - アルゴリズム学習(その4)

今回はスタックとキュー。非常に基本的なデータ構造だし、だいたい知っているけど、基本の本に書いてあることを全部再実装しようという方針なのでやってみる。

スタック

スタックは配列を普通に使って、次に入れる位置を保存しておけば実装できる。pushもpopもO(1)で計算できる。

public class IntStack {
    private int maxSize;
    private int[] data;
    private int top;

    public IntStack(int maxSize) {
        this.maxSize = maxSize;
        this.data = new int[maxSize];
        this.top = 0;
    }

    public void push(int x) {
        if (this.isFull()) {
            throw new RuntimeException("Stack is full");
        }

        this.data[this.top] = x;
        this.top++;
    }

    public int pop() {
        if (this.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }

        this.top--;
        return this.data[this.top];
    }

    public int size() {
        return this.top;
    }

    public boolean isEmpty() {
        return this.size() == 0;
    }

    public boolean isFull() {
        return this.size() == maxSize;
    }
}

確認のため、一応これはテストもちゃんと書いてみた。

import org.junit.Test;
import static org.junit.Assert.*;

public class IntStackTest {
    @Test
    public void stack() throws Exception {
        IntStack stack = new IntStack(3);
        assertTrue(stack.isEmpty());

        stack.push(10);
        stack.push(5);
        stack.push(3);

        assertTrue(stack.isFull());

        try {
            stack.push(1);
        } catch (RuntimeException e) {
            assertEquals("Stack is full", e.getMessage());
        }

        assertEquals(3, stack.pop());
        assertEquals(2, stack.size());

        assertEquals(5, stack.pop());
        assertEquals(1, stack.size());

        stack.push(4);
        assertEquals(2, stack.size());

        assertEquals(4, stack.pop());
        assertEquals(1, stack.size());

        assertEquals(10, stack.pop());
        assertEquals(0, stack.size());

        assertTrue(stack.isEmpty());

        try {
            stack.pop();
        } catch (RuntimeException e) {
            assertEquals("Stack is empty", e.getMessage());
        }
    }
}

キュー

キューは配列を循環して使うことで実装できる。例外処理は本当に単純作業だったので省いた。enqueueもdequeueもO(1)で計算できる。

public class IntQueue1 {
    private int size;
    private int[] data;
    private int top;
    private int maxSize;

    public IntQueue1(int maxSize) {
        this.maxSize = maxSize;
        this.top = 0;
        this.data = new int[maxSize];
        this.size = 0;
    }

    public void enqueue(int item) {
        this.data[ (this.top + this.size) % this.maxSize ] = item;
        this.size++;
    }

    public int dequeue() {
        int item = this.data[this.top];
        this.top = (this.top + 1) % this.maxSize;
        this.size--;
        return item;
    }

    public int getSize() {
        return this.size;
    }
}

こちらもテストを書いておく。

import org.junit.Test;
import static org.junit.Assert.*;
public class IntQueue1Test {
    @Test
    public void queue() throws Exception {
        IntQueue1 queue = new IntQueue1(3);

        queue.enqueue(10);
        queue.enqueue(5);
        queue.enqueue(3);

        assertEquals(10, queue.dequeue());
        assertEquals(2, queue.getSize());

        assertEquals(5, queue.dequeue());
        assertEquals(1, queue.getSize());

        queue.enqueue(4);
        assertEquals(2, queue.getSize());

        assertEquals(3, queue.dequeue());
        assertEquals(1, queue.getSize());

        assertEquals(4, queue.dequeue());
        assertEquals(0, queue.getSize());
    }

}

LinkedListによるキュー

LinkedListっぽくも出来るなーと思って、そちらも実装。firstとlastを保存しておけば、enqueueもdequeueもO(1)で計算できる。またLinkedListなので長さは可変にできる。ただしそれぞれの要素にnextというメタ情報が必要なため、余分にメモリは食う。

public class IntQueue2 {
    public int size;
    private IntQueue2Item first;
    private IntQueue2Item last;

    public IntQueue2 () { }

    public void enqueue(int value) {
        IntQueue2Item item = new IntQueue2Item(value);
        if (this.first == null) {
            this.first = item;
        }
        else {
            this.last.next = item;
        }
        this.last = item;
        this.size++;
    }

    public int dequeue() {
        IntQueue2Item item = this.first;
        this.first = this.first.next;
        this.size--;
        return item.value;
    }
}

class IntQueue2Item {
    IntQueue2Item next;
    int value;

    public IntQueue2Item(int value) {
        this.value = value;
    }

    public void setNext(IntQueue2Item item) {
        this.next = item;
    }
}