IntLinkedQueue 클래스

코드 설명

/******************************************************************************
 * IntLinkedQueue 클래스는 정수 큐를 연결 리스트로 구현한 클래스입니다.
 ******************************************************************************/
public class IntLinkedQueue implements Cloneable {
    // IntLinkedQueue 클래스의 불변 조건 (Invariant):
    //   1. 큐에 있는 항목 수는 manyNodes 변수에 저장됩니다.
    //   2. 큐에 있는 항목은 연결 리스트에 저장되며,
    //      큐의 앞부분은 head 노드(맨 앞 노드), 뒷부분은 마지막 노드에 해당합니다.
    //   3. 큐가 비어 있지 않은 경우, front는 리스트의 첫 노드를, rear는 마지막 노드를 참조합니다.
    //      큐가 비어 있는 경우, front와 rear는 둘 다 null입니다.
    private int manyNodes;
    private IntNode front;
    private IntNode rear;

    /**
     * 빈 큐를 초기화합니다.
     * @param - 없음
     * <dt><b>후조건:</b><dd>
     *   큐가 비어 있게 됩니다.
     **/
    public IntLinkedQueue() {
        front = null;
        rear = null;
        manyNodes = 0;
    }

    /**
     * 현재 큐의 복사본을 생성합니다.
     * @param - 없음
     * @return
     *   복사된 큐 객체가 반환됩니다. 복사본에 대한 변경은 원본에 영향을 주지 않으며, 그 반대도 마찬가지입니다.
     *   반환값은 <CODE>IntLinkedQueue</CODE> 타입으로 형변환되어야 사용 가능합니다.
     * @exception OutOfMemoryError
     *   복사 과정에서 메모리가 부족한 경우 발생합니다.
     **/
    public Object clone() {
        IntLinkedQueue answer;
        IntNode[] cloneInfo;

        try {
            answer = (IntLinkedQueue) super.clone();
        } catch (CloneNotSupportedException e) {
            // 이 예외는 발생하지 않아야 하지만, 발생하면 보통 super.clone을 사용할 수 없도록
            // Cloneable 인터페이스를 구현하지 않았다는 실수일 수 있습니다.
            throw new RuntimeException("이 클래스는 Cloneable을 구현하지 않았습니다.");
        }

        cloneInfo = IntNode.listCopyWithTail(front);
        answer.front = cloneInfo[0];
        answer.rear = cloneInfo[1];

        return answer;
    }

    /**
     * 큐의 앞 항목을 가져오고, 해당 항목을 큐에서 제거합니다.
     * @param - 없음
     * <dt><b>전제조건:</b><dd>
     *   큐가 비어 있지 않아야 합니다.
     * <dt><b>후조건:</b><dd>
     *   반환값은 큐의 앞 항목이며, 해당 항목은 큐에서 제거됩니다.
     * @exception NoSuchElementException
     *   큐가 비어 있는 경우 발생합니다.
     **/
    public int getFront() {
        int answer;

        if (manyNodes == 0)
            throw new NoSuchElementException("큐 언더플로우");
        answer = front.getData();
        front = front.getLink();
        manyNodes--;
        if (manyNodes == 0)
            rear = null;
        return answer;
    }

    /**
     * 큐에 새 항목을 삽입합니다.
     * @param <CODE>item</CODE>
     *   큐에 삽입할 항목입니다.
     * <dt><b>후조건:</b><dd>
     *   항목이 큐에 삽입됩니다.
     * @exception OutOfMemoryError
     *   큐의 용량을 늘릴 수 없을 정도로 메모리가 부족한 경우 발생합니다.
     * <dt><b>참고:</b><dd>
     *   용량을 <CODE>Integer.MAX_VALUE</CODE> 이상으로 증가하려고 하면
     *   정수 오버플로우로 인해 실패할 수 있습니다.
     **/
    public void insert(int item) {
        if (isEmpty()) {
            // 첫 항목 삽입
            front = new IntNode(item, null);
            rear = front;
        } else {
            // 첫 항목이 아닌 경우 삽입
            rear.addNodeAfter(item);
            rear = rear.getLink();
        }
        manyNodes++;
    }

    /**
     * 큐가 비어 있는지 확인합니다.
     * @param - 없음
     * @return
     *   큐가 비어 있으면 <CODE>true</CODE>, 아니면 <CODE>false</CODE>
     **/
    public boolean isEmpty() {
        return (manyNodes == 0);
    }

    /**
     * 큐에 저장된 항목의 수를 반환합니다.
     * @param - 없음
     * @return
     *   큐에 저장된 항목의 개수
     **/
    public int size() {
        return manyNodes;
    }
}

인스턴스 멤버

private int manyNodes;
private IntNode front;
private IntNode rear;

• manyItems는 데이터의 개수를 의미한다.
• front는 맨 앞의 노드를 가리키고 rear는 맨 뒤의 노드를 가리킨다.

생성자

public IntLinkedQueue() {
        front = null;
        rear = null;
        manyNodes = 0;
    }

• front, rear를 null로, manyNodes를 0으로 초기화시켜준다.

메서드

public Object clone() {
        IntLinkedQueue answer;
        IntNode[] cloneInfo;

        try {
            answer = (IntLinkedQueue) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new RuntimeException("이 클래스는 Cloneable을 구현하지 않았습니다.");
        }

        cloneInfo = IntNode.listCopyWithTail(front);
        answer.front = cloneInfo[0];
        answer.rear = cloneInfo[1];

        return answer;
    }

• (IntLinkedQueue) super.clone()로 얕은 복사를 해주고, IntNode에서 제공하는 listCopyWithTail로 front와 rear를 깊은 복사 해준다.

public int getFront() {
        int answer;

        if (manyNodes == 0)
            throw new NoSuchElementException("큐 언더플로우");
        answer = front.getData();
        front = front.getLink();
        manyNodes--;
        if (manyNodes == 0)
            rear = null;
        return answer;
    }

• 만약 데이터의 개수가 0이라면 에러를 발생시킨다.
• 아니라면 현제 위치의 데이터를 answer에 저장해 주고 front를 front와 연결된 링크로 이동시켜 준고 manyItems를 1 줄여준다.
• 만약 데이터의 개수가 0이라면 rear를 없음 처리해주어야 한다.

public void insert(int item) {
        if (isEmpty()) {
            // 첫 항목 삽입
            front = new IntNode(item, null);
            rear = front;
        } else {
            // 첫 항목이 아닌 경우 삽입
            rear.addNodeAfter(item);
            rear = rear.getLink();
        }
        manyNodes++;
    }

• 만약 데이터가 비어있다면 front에 데이터를 새로 추가해 주고 rear를 front로 지정해줘야 한다.
• 그리고 첫 항목이 아니라면 addNodeAfter를 활용하여서 이후에 넣어 주고, rear를 다음 Node로 지정해 주어야 한다.

public boolean isEmpty() {
        return (manyNodes == 0);
    }

    public int size() {
        return manyNodes;
    }

• isEmpty는 데이터의 개수가 0인 경우에 true 아니라면 false를 리턴해주면 된다.
• size는 manyNodes를 리턴해주면 된다.