자료구조 선형 큐 (Linear Queue) 자바로 구현

1. 개요

 

큐는 대표적인 자료구조중 하나로, 가장 먼저 들어간 데이터가 가장 먼저 나오는 선입선출, FIFO

(First In First Out) 형태의 자료구조다.

 

활용방법으로는

• 프린터 출력 (가장 먼저 대기열에 오른 프린트를 먼저 실행)
• 대기열, 대기표 (먼저 신청한 사람이 먼저 업무를 봄)
• 순서가 보장된 처리를 제공
• 사용자가 몰린 서버에 유

기능으로는

• offer() : 데이터 삽입
• poll() : 데이터 빼기
• peek() : 데이터를 뽑지 않고, 큐 안에서 가장 먼저 들어온 데이터 확인

 

 

2. 구현

package queue;

public interface IQueue<T> {
    void offer(T data);
    T poll();
    T peek();
    int size();
    void clear();
    boolean isEmpty();
}

package queue;

public class MyLinkedQueue<T> implements IQueue<T> {
// 노드 기반 큐
    private Node head;
    private Node tail;
    private int size;

    public MyLinkedQueue() {
        this.size = 0;
        this.head = new Node(null);
        this.tail = this.head; // head의 레퍼런스를 집어넣었으니 tail에서
        // 다른 레퍼런스를 집어넣기 전까진, head를 조작하는 것과 같다.
    }

    @Override

    public void offer(T data) {
        Node node = new Node(data);
        this.tail.next = node;
        this.tail = this.tail.next;
        this.size++;
    }

    @Override
    public T poll() {
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }
        Node node = this.head.next;
        this.head.next = node.next;
        node.next = null;
        this.size--;

        if (this.head.next == null) {
            this.tail = this.head;
        }

        return node.data;
    }

    @Override
    public T peek() {
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }
        return this.head.next.data;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public void clear() {
        this.head.next = null;
        this.tail = head;
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.head.next == null;
    }

    private class Node {
        T data;
        Node next;

        Node(T data) { this.data = data; }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

 

3. 설명

3-1. 노드 구성

 

data (데이터를 가지는 변수), next (다음 노드, 포인터의 역할)

인수로 data만 넣으면 노드에 데이터만 대입, data와 노드를 넣으면 노드에 데이터와 다음 노드를 대입한다.

 

3-2. 멤버 변수(Member Variable), 생성자(constructor)

선형 큐를 편하게 구현하려면, 데이터가 들어가지 않는 head와 tail이라는 노드가 필요하다.

그리고 큐의 크기를 나타내는 size가 있다.

 

인스턴스 생성 시, 생성자에서 size는 0, head에 빈 노드를 집어넣고, tail에 head를 집어넣는다.

자바에선 인스턴스 생성 시, 변수에 그 레퍼런스 주소가 들어가니, head와 tail은 같은 메모리 주소를

보고 있다.

 

 

3-3. offer()

데이터를 삽입하는 메소드다.

데이터를 집어넣기 위해, 인수로 들어온 데이터를 대입한 노드를 생성한다.

데이터가 없는 상태에선, tail은 head와 같으므로, this.tail.next = node 로 대입하면, head와 tail의 next는

데이터가 들어간 새로운 노드가 된다.

 

tail에 tail.next를 대입하게 되면, tail의 next는 새로운 노드이니, head는 그대로, tail은 새로운 노드가 된다.

정리하면

head(null, newNode1), tail(newNode1.data, null), newNode1(data, null);

 

한번 더 데이터가 들어오게 되면, 데이터가 들어간 2번째 노드가 생성되고, tail은 지금 newNode1이니, newNode1

의 next는 2번째 노드가 된다.

tail에 tail.next를 대입하면, tail은 2번째 노드가 되고, 정리하면

head(null, newNode1), tail(newNode2.data, null), newNode1(data, newNode2), newNode2(data,

null) 의 상태가 된다.

 

 

3-4. isEmpty()

큐에 데이터가 들어가 있나 확인하는 메소드다.

생성자에서 head의 next를 설정하지 않았으니, 데이터가 들어오지 않았으면 head.next는 null이고, true를

반환한다. 데이터가 있으면 head.next가 null이 아니므로, false를 반환한다.

 

 

3-5. poll()

큐에서 가장 먼저 들어온 데이터를 가져오고, 그 데이터를 큐에서 삭제하는 메소드다.

 

우선 큐가 비어있으면, 꺼낼 데이터가 없으니, isEmpty() 메소드로 확인하고, 없으면 에러를 발생시킨다.

 

데이터가 있으면, 데이터를 꺼내기 위해 새로운 노드를 생성하고, 가장 먼저 들어온 데이터가 있는, head.next

의 레퍼런스 주소를 대입한다.

 

가장 먼저 들어온 데이터 외에 데이터가 있다면, 가장 먼저 들어온 노드의 next에 저장되어 있으니, head.next

를 그걸로 바꿔준다.

 

그리고, 데이터를 꺼낼 노드의 next를 null로 바꿔주면, 이 메소드가 끝나게 되면, 이 노드를 참조하는 변수는 아무것도

없으니, 자바의 GC(Garbage Collector)에 의해 없어지게 된다.

 

데이터를 가진 노드가 하나 사라졌으니 사이즈를 1 줄여주고, 만약 데이터를 가진 노드가 없다면, offer() 메소드의

작업을 하기 위해, 생성자와 같이, this.tail = this.head의 형태로 레퍼런스를 대입한다.

 

그리고, 가장 먼저 들어온 노드의 데이터를 반환하고, 메소드가 끝나게 된다.

 

 

3-6. peek()

poll() 메소드와 다르게, 가장 먼저 들어온 노드를 삭제하지 않고, 노드의 데이터만 반환받는 메소드다.

 

만약, 큐가 비었으면 에러를 일으킨다. 그게 아니라면 head.next는 가장 먼저 들어온 데이터가 들어간 노드이니,

그 데이터를 반환하고 메소드가 종료된다.

 

 

3-7. size()

큐의 사이즈를 반환하는 메소드다.

 

 

3-8. clear()

큐 안에 데이터가 있는 노드를 모두 삭제하는 메소드다.

 

head.next에 가장 먼저 들어온 데이터를 가진 노드가 있고, 그 노드부터 다른 노드로 이어져 있는 큐인데,

가장 먼저 들어온 노드의 참조를 null로 끊고, 마지막 데이터가 있는 tail을, 데이터와 포인터가 모두 비어있는

head로 초기화하면서, 데이터가 있는 노드들은 GC에 의해 삭제되고, 큐에는 빈 노드인 head와 tail만 남는다.

 

데이터가 들어간 노드가 없으니 사이즈에 0을 대입하고 메소드가 종료된다.