[자료구조-04] 큐(Queue)

1. 큐(Queue)란?

 

큐의 구조

 

- 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조

- 선입선출 구조를 가짐

- 선입선출(FIFO, First In First Out) : 가장 먼저 넣은 데이터를 가장 먼저 꺼냄

 

- 인큐(enqueue) : 큐에 데이터를 넣는 작업

  디큐(dequeue) : 큐에서 데이터를 꺼내는 작업

  프런트(front) : 데이터를 꺼내는 쪽

  리어(rear) : 데이터를 넣는 쪽

 

- 예) 은행 창구에서 차례를 기다리는 대기열, 마트에서 계산을 기다리는 대기열

 

 

2. 배열로 큐 구현

- 스택과 마찬가지로 배열로 큐를 구현할 수 있음

- 하지만 효율성이 떨어짐

 

(1) 인큐(enqueue)

 

 

- 32를 인큐

- 데이터를 넣기만 하면 되기 때문에 복잡도는 O(1)

- 적은 비용으로 구현 가능

 

 

(2) 디큐(dequeue)

 

- 54를 디큐

- 나머지 데이터들을 한 칸씩 앞으로 이동해야 함(shift)

- 복잡도는 O(n)

- 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어짐

 

3. 링 버퍼로 큐 구현

1) 링 버퍼(ring buffer)

링 버퍼의 구조

 

- 배열의 처음이 끝과 연결되었다고 보는 자료구조

- 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수로 프런트(front)와 리어(rear)를 사용

- 프런트(front) : 맨 처음 요소의 인덱스

  리어(rear) : 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐할 위치를 미리 지정

- 논리적인 데이터 순서일 뿐 물리적 요소의 순서는 아님

 

- 배열과 달리 프런트와 리어 값을 업데이트하며 인큐와 디큐를 수행하기 때문에, 요소 이동을 하지 않아도 돼서 처리의 복잡도는 O(1)임

2) 필드

class IntQueue {
    int max;	// 큐의 용량
    int front;	// 첫 번째 요소 커서
    int rear;	// 마지막 요소 커서
    int num;	// 현재 데이터 수
    int[] que;	// 큐 본체
 }

 

(1) 큐로 사용할 배열 que

- 인큐하는 데이터를 저장하기 위한 큐 본체용 배열

- 실제 배열 본체가 아닌 본체를 참조하는 배열 변수

 

(2) 큐의 최대 용량 max

- 큐의 최대 용량을 저장하는 필드

- 배열 que에 저장할 수 있는 최대 요소의 개수와 같음

 

(3) 프런트(front)

- 인큐하는 데이터 가운데 첫 번째 요소의 인덱스를 저장하는 필드

 

(4) 리어(rear)

- 인큐한 데이터 가운데 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장하는 필드

 

(5) 현재 데이터 수 num

- 큐에 쌓아 놓은 데이터 수

 

 

※ num을 사용하는 이유?

- front와 rear의 값이 같은 경우 큐가 비어있는지 가득 찼는지 구별할 수 없는 상황이 발생함

- 이를 구별하기 위해 num을 사용

- 큐가 비어 있을 때 num = 0

- 큐가 가득 찼을 때 num = max

 

 

3) 생성자

public IntQueue(int capacity) {
    num = front = rear = 0;
    max = capacity;
    try {
    	que = new int[max];			// 큐 본체용 배열을 생성
    } catch(OutOfMemoryError e) {
    	max = 0;
    }
}

 

- 큐 본체용 배열을 생성하는 등의 준비 작업을 수행

 

(1) 생성 시 큐는 비어 있기 때문에 num, front, rear 값을 모두 0으로 함

(2) 매개변수 capacity로 전달받은 큐의 용량을 max에 복사

(3) 요솟수가 max인 배열 que의 본체를 생성

 

4) 인큐(enqueue)

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

 

- 큐에 데이터를 인큐하는 메서드

- 인큐에 성공하면 인큐한 값을 그대로 반환

- 인큐할 수 없으면(num >= max가 성립하면) 예외 OverflowIntQueueException을 던짐

 

(1) 전달받은 데이터 x를 배열 요소 que[rear]에 저장

(2) 끝+1을 나타내는 rear을 증가시킴

(3) 현재 데이터 수 num을 증가시킴

(4) rear이 max와 같아지면 실제 배열에는 없는 공간을 가리키므로 rear을 0으로 만들어줌

 

5) 디큐(dequeue)

public int deque() throws EmptyIntQueueException {
    if (num <= 0)
    	throw new EmptyIntQueueException();
    int x = que[front++];
    num--;
    if (front == max)
    	front = 0;
        
    return x;
}

 

- 큐에 데이터를 디큐하는 메서드

- 디큐에 성공하면 디큐한 값을 그대로 반환

- 디큐할 수 없으면(num <= 0이 성립하면) 예외 EmptyIntQueueException을 던짐

 

(1) 반환할 변수 x에 que[front]를 저장

(2) 처음을 의미하는 front를 증가시킴

(3) 현재 데이터 수 num을 감소시킴

(4) front가 max와 같아지면 실제 배열에는 없는 공간을 가리키므로 front를 0으로 만들어줌

 

6) 피크(peek)

public int peek() throws EmptyIntQueueException {
    if (num <= 0)
    	throw new EmptyIntQueueException();
    return que[front];
}

 

- 큐의 맨 앞의 데이터를 몰래 엿보는 메서드

- que[front]의 값을 조사만 하고 데이터를 꺼내지는 않으므로 front, rear, num의 값이 변화하지 않음

 

7) 기타 메서드

// (1) 요소 검색
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;					// 검색 실패
}

// (2) 모든 요소 삭제
public void clear() {
    num = front = rear = 0;
}

// (3) 큐의 용량 반환
public int capacity() {
    return max;
}

// (4) 데이터 수 확인
public int size() {
    return num;
}

// (5) 비어있는지 확인
public boolean isEmpty() {
    return num <= 0;
}

// (6) 가득찼는지 확인
public boolean isFull() {
    return num >= max;
}

// (7) 큐 안의 모든 데이터를 바닥 -> 꼭데기 순서로 출력
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();
    }
}

 

 

 

 

 

 

참고 - Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 (저자 : 보요 시바타, 출판 : 이지스 퍼블리싱)