자료구조 큐(queue) - 선형 큐, 원형 큐 | 덱(deque)

큐(queue)

 

- 먼저 들어온 데이터가 먼저 나가는 선입선출 구조.

- FIFO( First In, First Out)

- ex) 매표소 대기줄 

- 전단(front) 은 가장 먼저 들어오는 데이터를, 후단(rear)는 가장 마지막에 들어오는 데이터를 가리킨다.  

- 삽입 : enqueue()는 큐의 후단(rear)에서,

- 삭제 : dequeue()큐의 전단(front)에서 이루어 진다.  

- init() : 초기화

- is_empty() : 큐가 비어있으면 true, 아니면 false 반환한다.

- peek() : 큐가 비어있지 않으면 맨 앞 요소를 삭제하지 않고 반환한다.

- is_full() : 큐가 가득 차 있으면 true, 아니면 false 반환한다.

- size() : 큐의 모든 요소들의 개수를 반환한다.

 

- queue 의 응용 -> 은행 시뮬레이션

 1. 매표소 대기줄 : 창구를 더 늘리기 전, 자신들이 감당할 수 있는 정도를 시뮬레이션 한 후 결정한다.

    · 입력: 시뮬레이션 할 최대시간, 단위 시간에 도착하는 고객 수, 한 고객에 대한 최대 서비스 시간

    · 출력: 고객 평균 대기 시간

    · 서비스 인원(은행원)

    · 고객정보 등 고려 -> 서비스 시간 = 서비스 끝난 시간 - 고객도착시간

 2. 통신에서 데이터 패킷들의 모델링에 이용 : 메시지를 패킷으로 잘라 번호를 부여해 보낸 후, 목적지에 도달했을 때 다시 조립(assembly)한다. 

 3. 프린터와 컴퓨터 사이 버퍼링 : cpu가 다른 일하다가 버퍼에 쌓인 일을 한꺼번에 처리한다.

    - 출력 인쇄 버퍼: 보낸 순서대로 처리한다.

    - ※ 예외: 우선순위가 높은 것이 들어오면 그것을 먼저 처리한다.

 

※ 스타베이션: 우선순위가 높은 것들로 인해 낮은 것들이 계속 뒤로 밀리는 현상.

이를 해결하기 위해, 에이징 기법 사용.

 

※ 에이징 기법: 대기시간이 오래된 것의 우선순위를 높여준다. 

 

- 선형 큐

 요소들을 삭제하고 비어있는 자리들이 그대로 남아 공간을 차지하고 있으므로 포화 상태가 되면 새로운 요소를 더이상 삽입할 수없고 공간낭비를 한다. 이를 개선하기 위해 원형 큐를 이용한다.

 

- 원형 큐

 · 선형 큐 단점을 보완하기 위해 배열을 원형으로 사용하여 큐를 구현.

 · 전단과 후단을 관리하기 위한 2개의 변수 필요

 · front : 첫번째 요소 하나 앞의 인덱스   

 · rear : 마지막 요소의 인덱스 

 · 공백상태 : front == rear

 · 포화상태 : front % M == (rear+1) % M

 · 공백상태와 포화상태 구별하기 위해 0번째 배열을 항상 비워둔다. 

 · 나머지 연산을 사용하여 인덱스를 원형으로 회전시킨다. 

 

<원형 큐의 연산>

 

 · 삽입 연산

   enqueue(x)

   rear ← (rear+1) mod MAX_QUEUE_SIZE;

   data[rear] ← x;  

 · 삭제 연산

   dequeue(x)

   front ← (front+1) mod MAX_QUEUE_SIZE;

   return data[front];

 · 원형 큐의 데이터

  - int 큐에서 Element는 int로 지정

  - 전역변수 사용

 

- 덱(deque)

 · double-ended queue

 · 전단과 후단에서 모두 삽입과 삭제가 가능한 큐

 · init() : 초기화

 · add_front() : 요소를 맨 앞에 추가

 · add_rear() : 요소를 맨 뒤에 추가

 · delete_front() : 전단 요소를  삭제 후 반환한다.

 · delete_rear() : 후단 요소를  삭제 후 반환한다.

 · get_front() : 전단 요소를 삭제하지 않고 반환한다.

 · get_rear() : 후단 요소를 삭제하지 않고 반환한다.

 

- 원형 덱

 · 큐와 데이터 동일, 연산 유사

<원형 덱의 연산>

 · 덱에서 추가된 연산 

delete_rear(), add_front(), get_real()

 · 반대 방향의 회전 필요

front ← (front-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;

rear ← (rear-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;