[Data Structure] 큐 (Queue)개념 및 구현

큐 (Queue)

큐는 사전적 의미로 줄을 서서 기다리다, 대기열이라고 정의되어 있다.

단어로 짐작할 수 있듯이 가장 마지막에 추가된 데이터가 가장 먼저 삭제되는 스택과는 반대로 먼저 추가된 데이터가 먼저 삭제되는 선입선출 형태의 자료구조이다.

 

큐 사용 예제

• 은행이나 상담원 연결 대기번호 
• 프린터 인쇄 대기열
• BFS

---

큐의 특징

1. FIFO (First In First Out)

먼저 들어간 데이터가 가장  처음에 나오는 선입선출의 자료구조

 

2. 데이터는 하나씩 추가 / 삭제

데이터가 아무리 많아도 하나씩만 추가하거나 삭제할 수 있다.

 

3. 두 개의 입출력 방향

추가와 삭제의 방향이 같은 스택이랑 다르게 추가 삭제 방향이 다르다

---

큐 주요 메서드 및 구현

add()   - 큐에 데이터 추가
poll()   - 가장 처음에 추가된 데이터를 큐에서 삭제하고 데이터를 반환
peek() - 가장 처음에 추가된 데이터를 반환 (삭제 X)
size()  -  큐에 저장되어 있는 데이터의 개수 반환
clear() - 큐의 모든 데이터 삭제
isEmpty() - 큐가 비었는지 boolean으로 반환

큐를 구현하기 위해 LinkedList를 사용했다. LinkedList는 다음 링크에서 확인할 수 있다.

https://dongs-record.tistory.com/17

 

QueueNode

class QueueNode<T> {
    private T data;
    private QueueNode<T> next;

    public QueueNode(T data) {
        this.data = data;
        this.next = null;
    }

    public T getData() {
        return data;
    }

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

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

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

노드로 사용할 QueueNode 정의

 

MyQueue

class MyQueue<T> {
    private int size;
    private QueueNode<T> head;

    public MyQueue() {
        this.size = 0;
        head = null;
    }

    public void add(T data) {
        QueueNode<T> newNode = new QueueNode<>(data);

        if (head == null) {
            head = newNode;
        } else {
            QueueNode<T> temp = head;
            while (temp.getNext() != null) {
                temp = temp.getNext();
            }
            temp.setNext(newNode);
        }
        size++;
    }

    public T poll() {
        if(head == null){
            return null;
        }
        QueueNode<T> removeNode = head;
        head = removeNode.getNext();

        T data = removeNode.getData();
        removeNode = null;
        size--;

        return data;
    }

    public T peek() {
        if(head == null){
            return null;
        }
        return head.getData();
    }

    public void clear() {
        QueueNode<T> temp = head;
        while(temp.getNext() != null){
            QueueNode<T> next = temp.getNext();
            temp.setNext(null);
            temp.setData(null);
            temp = next;
        }
        head = null;
        size = 0;
    }

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

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

    public String toString() {
        if (head == null) {
            return "[]";
        }
        QueueNode<T> temp = head;
        String str = "[";
        while (temp.getNext() != null) {
            str += temp.getData() + ", ";
            temp = temp.getNext();
        }

        str += temp.getData();
        str += "]";

        return str;
    }

}

 

MyQueue()

public MyQueue() {
    this.size = 0;
    head = null;
}

MyQueue의 생성자 

head를 null로 size를 0으로 초기화한다.

 

add()

public void add(T data) {
    QueueNode<T> newNode = new QueueNode<>(data);

    if (head == null) {
        head = newNode;
    } else {
        QueueNode<T> temp = head;
        while (temp.getNext() != null) {
            temp = temp.getNext();
        }
        temp.setNext(newNode);
    }
    size++;
}

큐에 데이터가 없을 때 head가 null이므로 head를 newNode로 설정한다.

아닐 경우 노드들을 순회하며 next가 null인 노드의 next로 newNode를 설정한다.

 

poll()

public T poll() {
    if(head == null){
        return null;
    }
    QueueNode<T> removeNode = head;
    head = removeNode.getNext();

    T data = removeNode.getData();
    removeNode = null;
    size--;

    return data;
}

큐에 데이터가 없을 경우엔 null을 반환하고 아니면 head가 가리키고 있는 노드의 데이터를 반환하고 노드를 삭제

 

peek()

public T peek() {
    if(head == null){
        return null;
    }
    return head.getData();
}

head 노드의 데이터를 반환

 

clear()

public void clear() {
    QueueNode<T> temp = head;
    while(temp.getNext() != null){
        QueueNode<T> next = temp.getNext();
        temp.setNext(null);
        temp.setData(null);
        temp = next;
    }
    head = null;
    size = 0;
}

head 노드부터 순회하면서 노드를 제거

 

isEmpty() & size()

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

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

데이터의 개수를 반환하는 size()와 큐가 비어있는지 boolean 타입으로 반환한다.

 

public class QueueTest {
    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>();
        for(int i = 0; i < 3; i++){
            queue.add(i);
        }

        System.out.println("queue.size = " + queue.size() + " q.peek() = " + queue.peek());
        System.out.println("queue = " + queue);
        queue.poll();
        
        System.out.println("--------------queue.poll()--------------");
        System.out.println("queue.size = " + queue.size() + " q.peek() = " + queue.peek());
        System.out.println("queue = " + queue);

        System.out.println("--------------queue.add()--------------");
        for(int i = 3; i < 12; i++){
            queue.add(i);
        }
        System.out.println("queue.size = " + queue.size() + " q.peek() = " + queue.peek());
        System.out.println("queue.isEmpty() = " + queue.isEmpty());
        System.out.println("queue = " + queue);

        System.out.println("--------------queue.clear()------------");
        queue.clear();
        System.out.println("queue.clear(), queue = " + queue);
        System.out.println("queue.isEmpty() = " + queue.isEmpty());
    }
}