본문 바로가기

대학교 2학년 1학기/자료구조

5. 큐

728x90

1. 큐의 특징 

- 선입 선출: 먼저 들어온 데이터가 먼저 나감. 

- 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조. 

- 삽입이 일어나는 곳을 후단, 삭제가 일어나는 곳을 전단이라고 함. 

- 삽입과 관련된 변수를 rear, 삭제와 관련된 변수를 front라고 함.

 

큐의 추상 자료형 

- create(max_size): 최대 크기가 max_size인 공백큐를 생성.

- init(q): 큐를 초기화.

- is_empty(q): 큐가 공백상태인지 검사.

- is_full(q): 큐가 포화상태인지 검사.

- enqueue(q, e): 큐의 끝에 데이터를 추가.

- dequeue(q): 큐의 앞에 있는 데이터를 삭제하고 반환. 

- peek(q): 큐의 맨 앞에 있는 데이터를 읽어서 반환.

 

2. 선형큐 

- 1차원 배열을 써서 정수를 저장할 수 있는 큐.

- front는 큐의 첫 번째 요소의 하나 앞을 가리키고 rear는 큐의 마지막 요소를 가리킴. 

- front와 rear의 초기값은 -1

- 데이터가 증가되면 rear를 하나 증가하고 그 위치에 있는 데이터가 저장. 

- 삭제할 때는 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제.

문제점: front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되며 배열의 앞부분이 비어 있더라도 사용하지를 못함. 따라서 주기적으로 모든 요소를 왼쪽으로 이동해야 하는데 프로그램이 복잡해짐. 

 

3. 원형큐

- front와 rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것. 

- front와 rear의 초기값은 -1이 아닌 0.

- front는 항상 큐의 첫 번째 요소의 하나 앞, rear는 마지막 요소를 가리킴. 

- 삽입 시 rear가 먼저 증가되고, 새로운 데이터가 삽입. 

- 삭제 시 front가 먼저 증가되고, 증가한 위치에서 데이터를 삭제. 

- front와 rear의 값이 같으면 원형 큐가 비어 있음을 나타냄. (공백상태) 

- 원형큐에서 포화 상태와 공백 상태를 구별하기 위해 하나의 자리는 항상 비워둠. 

- front가 rear보다 하나 앞에 있으면 포화 상태를 나타냄. (q->rear + 1) % MAX_QUEUE_SIZE == q->front

 

원형큐의 삽입, 삭제 알고리즘

- rear 삽입 q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;

- front 제거 q->front = (q->front + 1) % MAX_QUEUE_SIZE;

 

원형큐의 구현

 

error(mesg)

 

 

init(q)

 

 

is_empty(q)

 

 

is_full(q)

 

 

enqueue(q,item)

 

 

dequeue(q)

 

 

peek(q)

 

4. 덱

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

 

덱의 추상 자료형

- create(): 덱을 생성

- init(dq): 덱을 초기화

- is_empty(dq): 덱이 공백 상태인지를 검사

- is_full(dq): 덱이 포화 상태인지를 검사

- add_front(dq, e): 덱의 앞에 요소를 추가 

- add_rear(dq, e): 덱의 뒤에 요소를 추가 ( == enqueue(q, e) )

- delete_front(dq): 덱의 앞에 있는 요소를 반환한 다음 삭제 ( == dequeue(q) )

- delete_rear(dq): 덱의 뒤에 있는 요소를 반환한 다음 삭제

- get_front(q): 앞에 있는 요소를 삭제하지 않고 반환 ( == peek(q) )

- get_rear(q): 뒤에 있는 요소를 삭제하지 않고 반환

 

덱의 추가 삭제, 삽입 알고리즘

- front 삽입(q->front-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;

- rear 제거 : (q->rear-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;

 

덱의 구현

add_rear(q, item)

 

 

 

delete_front(q)

 

 

 

add_front(q, val)

 

 

 

delete_rear(q)

 

 

 

get_rear(q)

 

 

get_front(q)

 

 

 

728x90

'대학교 2학년 1학기 > 자료구조' 카테고리의 다른 글

6-2. 연결리스트 (단순 연결 리스트)  (0) 2022.05.03
6-1. 연결리스트 (배열을 이용한 구현)  (0) 2022.05.03
4. 스택  (0) 2022.04.11
3. 배열, 구조체, 포인터  (0) 2022.04.11
2. 순환  (0) 2022.04.11