큐(Queue)

큐 개념

큐 : 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조

• 선입선출(First-In First-Out, FIFO) 원칙하에 item 삽입과 삭제 수행
• CPU의 태스크 스케쥴링, 네트워크 프린터, 실시간 시스템의 인터럽트 처리, 다양한 이벤트 구동 방식 컴퓨터 시뮬레이션 등에 사용
• 이진트리의 레벨 순회와 그래프의 너비우선 탐색에 사용

• enQueue (add) : 큐의 맨 뒤에 새로운 요소 추가
• deQueue (remove) : 큐의 맨 앞의 요소 삭제
• front : 처음 부분
• rear : 마지막 부분

배열로 큐 구현하기

배열을 사용하였을 때의 문제점

-> 큐에서 삽입과 삭제를 거듭하게 되면 새 item들은 뒤에 삽입되고 삭제는 앞에서 일어나기 때문데 큐의 item들이 배열의 오른쪽으로 편중되는 문제 발생!

해결방안

1) 큐의 item들을 배열의 앞부분으로 이동 -> 수행시간이 큐에 들어있는 item의 수에 비례한다는 단점
2) 배열을 원형으로, 즉, 배열의 마지막 원소가 첫 원소에 맞닿아 있다고 여김

새 item 삽입 후

• 배열의 앞뒤가 맞닿아 있다고 생각하기 위해 배열의 rear 다음이 비어있는 원소의 인덱스
• rear = (rear+1) % N(N: 배열의 크기)

연속된 삭제 수행 시 문제점

연속된 삭제 연산 수행 시 큐의 마지막 item을 삭제한 후 큐가 empty임에도 rear은 삭제된 item을 가리키고 있다.

큐가 empty일 때 해결방안

1) item을 삭제할 때마다 큐가 empty가 되는지 검사하고 empty라면 front = rear = 0

-> 삭제할 때마다 조건 검사하는 것은 효율성 저하

2) front를 실제 가장 앞에 있는 item의 바로 앞의 비어있는 원소를 가리키게 하기

• 배열의 크기가 N이라면 실제 N-1개의 공간만 item들을 저장하는데 사용
  

empty가 되면 front == rear이 된다

구현

클래스

public class ArrayQueue <E>{
    private E[] q;  // 큐를 위한 배열
    private int front, rear, size;
    public ArrayQueue() {   // 생성자
        q = (E[])new Object[2]; // 초기에 크기가 2인 배열 생성
        front = rear = size = 0;
    }
    // size(), isEmpty(), add(), remove(), resize() 메소드
 }

삽입 연산

    public void add (E newItem){
        // 비어있는 원소가 1개뿐인 경우(큐가 full)
        if((rear+1)%q.length == front) // (rear+1)%q.length : rear 다음 원소의 인덱스
            resize(2*q.length); // 큐의 크기를 2배로 확장
        rear = (rear+1) % q.length;
        q[rear] = newItem;  // 새 항목을 add
        size++;
    }

데이터의 마지막 부분에 데이터 삽입이 일어나므로 rear 다음인 rear+1 위치에 데이터를 삽입한다.

삭제 연산

 public E remove(){
        if(isEmpty()) throw new NoSuchElementException(); // 언더플로우시 프로그램 정지
        front = (front+1) % q.length;
        E item = q[front];
        q[front] = null;
        size--;
        if(size > 0 && size == q.length/4)  // 큐의 항목수가 배열 크기의 1/4가 되면
            resize(q.length/2); // 큐를 1/2 크기로 축소
        return item;
    }

가장 먼저 들어온 데이터인 맨 앞 요소를 삭제한다. front가 가리키는 요소인 front+1이 null로 삭제되고 front는 front+1이 된다.

결과

큐에 대한 삽입, 삭제 연산 후 큐의 내용을 출력해보았다. front는 빨간색 박스, rear은 파란색 박스로 표시하였다.

연결리스트로 큐 구현하기

구현

클래스

public class ListQueue <E>{
    private Node<E> front, rear;
    private int size;
    public ListQueue() {
        front = rear = null;
        size = 0;
    }
    // size(), isEmpty(), add(), remove() 메소드
}

삽입 연산

 public void add(E newItem){
        Node newNode = new Node(newItem, null);
        if (isEmpty()) front = newNode;
        else rear.setNext(newNode);
        rear = newNode;
        size++;
    }

새 item을 큐의 뒤인 rear에 삽입한다. rear가 참조하는 노드의 next가 새로운 노드를 가리키도록하고 그 노드를 rear가 가리키게 한다.

삭제 연산

    public E remove() {
        // 언더플로우 발생 시 프로그램 정지
        if(isEmpty())   throw new NoSuchElementException();
        // front가 가리키는 노드의 항목을 frontItem에 저장
        E frontItem = front.getItem();
        // front가 front 다음 노드를 가리키게 한다
        front = front.getNext();
        // 큐가 empty면 rear = null
        if(front==null) rear = null;
        size--;
        return frontItem;
    }

큐의 앞의 item을 삭제한다. front가 가리키고 있는 노드의 item을 리턴하고 그 노드의 next 노드를 front가 참조하도록 한다.

수행시간

• 배열로 구현한 큐의 add / remove : O(1)
• -> 배열의 크기를 확대 또는 축소 시키는 경우에 큐의 모든 item들을 새 배열로 복사해야 하므로 O(N)시간 소요
• 단순연결리스크로 구현한 큐의 add /remove : O(1)
• -> 삽입 또는 삭제 연산이 rear와 front로 인해 연결리스트의 다른 노드들을 일일이 방문할 필요가 없다

데크(Deque)

개념

데크 - Double-ended Queue, Deque

• 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조
• 스택과 큐를 혼합한 자료구조
• 스택과 큐를 동시에 구현하는데 사용

응용

1) 스크롤(Scroll)
2) 웹 브라우저의 방문 기록 등

• 웹 브라우저 방문 기록의 경우, 치근 방문한 웹 페이지 주소는 앞에 삽입하고 일정 수의 새 주소들이 앞쪽에 삽입되면서 뒤에서 삭제가 수햄
  3) 개수 제한이 있는 문서 편집기의 undo

구현

배열로 구현한 데크

큐 자료구조와 같이 front가 실제 가장 앞에 있는 item의 앞 원소를 가리킨다.

이중연결리스트로 구현한 데크

rear가 가리키는 노드의 이전 노드의 레퍼런스를 알아야 삭제가 가능하기 때문에 이중연결리스트로 구현하는 것이 더 편리하다.

수행시간

• 데크를 배열이나 이중연결리스트로 구현한 경우, 스택과 큐의 수행시간과 동일
• 양 끝에서 삽입과 삭제가 가능하므로 프로그램이 다소 복잡
• 이중연결리스트로 구현한 경우 더 복잡함

스택, 큐, 데크 수행시간 비교