[데이터 구조] 16차시 큐(Queue) | 연결표현, 리스트를 이용한 Queue의 구현, 우선순위 Queue와 Deque

1. 큐의 연결 표현

1) Queue의 연결 표현

(1) 연결된 큐(linked queue): 연결 리스트로 구현된 큐

- front 포인터는 삭제와 관련되며 rear 포인터는 삽입과 관련됨

- front는 연결 리스트의 맨 앞에 있는 요소를 가리키며, rear 포인터는 맨 뒤에 있는 요소를 가리킴

- 큐에 요소(Element)가 없는 경우(Empty)에는 front와 rear는 NULL

 

(2) 연결된 큐에서의 삽입과 삭제

 

 

 

2) 리스트를 이용한 Queue의 구현

 

3) 큐를 1연결 리스트로 구현한 C 프로그램

 

 

 

2. 우선 순위 큐와 덱

1) 우선순위 Queue

(1) 정의

• 원소에 부여된 우선순위(priority)에 따라 우선순위가 가장 높은 원소부터 삭제하는 자료 구조
• Stack과 Queue도 우선순위 큐의 일종
  - Stack: 삽입 시간이 가장 짧은 원소에 가장 높은 우선순위를 부여한 우선순위 큐
  - Queue: 삽입 시간이 가장 오래된 원소에 가장 높은 우선순위를 부여한 우선순위 큐
  
  
• 원소의 우선순위 표현과 연산
  - 큐 안에 있는 원소의 우선순위는 우선순위(priority)를 나타내는 key 값으로 표현한다.
  - 삭제 연산: 우선순위가 가장 높은 원소가 제일 먼저 삭제
  - 삽입 연산: 우선순위와 관계 없이 임의의 순서로 삽입
  
  

(2) 우선순위 큐(priority queue) 추상 데이터 타입

(3) 원소들의 비교 연산

• 우선순위 큐의 원소들에 대해서는 다음과 같은 전체 순서(total order) 관계가 성립

• 우선순위 큐의 모든 원소는 우선 순위에 따라 일렬로 정렬 가능

(4) 우선 순위 큐의 구현

• 정렬된 연결 리스트(sorted linked list)를 이용하는 방법
• 무정렬 배열(unsorted array)을 이용하는 방법

(5) C에서의 우선순위 큐

 

• 우선순위 큐 정렬(priority queue sorting)
  - 정렬이 안된 어떤 배열(x)의 원소를 오름차순으로 정렬하고자 할 때, 아래 제시된 "우선순위 큐 프로그램"의 parameter (int * a)로 (x)의 주소(&x)를 call-by-reference로 전달해서 (x)의 원본 내용을 정렬할 수 있다.

 

 

2) Deque(덱)

(1) 정의: deque(덱)은 double-ended queue의 줄임말로, 큐의 전단(front)와 후단(rear)에서 삽입과 삭제가 모두 가능한 큐

 

(2) Deque ADT

Deque 연산

 

(3) Deque(덱) 구현
- 양쪽에서 삽입, 삭제가 가능하여야 하므로 일반적으로 이중연결 리스트를 사용

 

(4) Deque(덱) 삽입

- 양방향 연결리스트의 연산과 유사
- 헤드 포인터를 사용하지 않고, head와 tail 포인터를 사용함

 

(5) Deque(덱) 삭제