큐 정의

큐(Queue)는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조입니다.
생활에서 볼 수 있는 큐의 예는 은행 창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열을 들 수 있습니다.
큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 합니다.
또 데이터를 꺼내는 쪽을 프런트(front)라 하고, 데이터를 넣는 쪽을 리어(rear)라고 합니다.

큐 메서드

• enque(): 큐에 데이터를 인큐하는 메서드입니다. 인큐에 성공하면 인큐한 값을 그대로 반환합니다.
  그리나 큐가 가득 차서 인큐할 수 없으면 예외 OverflowIntQueueException을 던집니다.

  public int enque(int x) throws OverflowIntQueueException {
        if (num >= max)
            throw new OverflowIntQueueException();			// 큐가 가득 참
        que[rear++] = x;
        num++;
        if (rear == max)
            rear = 0;
        return x;
    }
  

• deque(): 큐에서 데이터를 디큐하고 그 값을 반환하는 메서드입니다. 그러나 큐가 비어 있어 디큐할 수 없으면
  예외 EmptyIntQueueException을 던집니다.

  public int deque() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();				// 큐가 비어 있음
        int x = que[front++];
        num--;
        if (front == max)
            front = 0;
        return x;
    }
  

• peek(): 맨 앞의 데이터를 “몰래 엿보는” 메서드입니다. que[front]의 값을 조사만 하고 데이터를 꺼내지는 않으므로
  front, rear, num의 값이 변화하지 않습니다. 큐가 비어 있으면 예외 EmptyIntQueueException을 던집니다.

  public int peek() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();				// 큐가 비어 있음
        return que[front];
    }
  

• IndexOf(): 큐의 배열에서 x와 같은 데이터가 저장되어 이쓴ㄴ 위치를 알아내는 메서드입니다.

  public int indexOf(int x) {
        for (int i = 0; i < num; i++) {
            int idx = (i + front) % max;
            if (que[idx] == x)								// 검색 성공
                return idx;
        }
        return -1;											// 검색 실패
    }
  

• clear(): 모든 데이터를 삭제하는 메서드

  public void clear() {
        num = front = rear = 0;
    }
  

• capacity(): 최대 용량을 확인하는 메서드

  public int capacity() {
        return max;
    }
  

• size(): 데이터 수를 확인하는 메서드

  public int size() {
        return num;
    }
  

• IsEmpty(): 큐가 비어 있는지 판단하는 메서드

  public boolean isEmpty() {
        return num <= 0;
    }
  

• IsFull(): 큐가 가득 찼는지 판단하는 메서드

  public boolean isFull() {
        return num >= max;
    }
  

• dump(): 모든 데이터를 출력하는 메서드

  public void dump() {
        if (num <= 0)
            System.out.println("큐가 비어 있습니다.");
        else {
            for (int i = 0; i < num; i++)
                System.out.print(que[(i + front) % max] + " ");
            System.out.println();
        }
    }
  

  
  

큐(Queue)의 사용 사례

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 너비 우선 탐색(BFS, Breadth-First Search) 구현
  • 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
  • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
  • 노드를 접근한 순서대로 처리할 수 있다.
• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리
  
  

참조

• 자료구조와 함께 배우는 알고리즘 입문 (자바 편)
• HeeJeong Kwon Blog