6장 큐 / 데크

큐

- 선입선출 구조(FIFO)

- 첫 번째 원소: flont / 마지막 원소: rear 

큐의 모습

스택과 다르게 먼저 들어간 원소가 먼저 빠진다.

 

큐의 주요 상태:

초기 상태: front = rear = -1

포화 상태: rear = n-1

공백 상태

 -> 큐의 포화 상태에서 끝까지 delete 했을 때 모든 원소가 사라진 공백 상태가 된다.

 

큐의 단점:  표류 현상 

          -> delete로 인해 비워진 공간들이 있음에도 불구하고 이미 rear를 했기 때문에 더 이상 삽입 연산을 할 수 없음.

해결책 1. shift 연산: 비워진 공간으로 원소를 일일이 옮긴다 -> 개힘듦

          2. 원형큐 -> 원형큐가 뭘까? 이제부터 알아보자

 

원형큐

선형큐의 논리적인 구조에서 마지막 인덱스가 첫 번째 인덱스와 붙어있음.

원형큐의 모습

원형큐의 주요 상태: 

초기 상태: front = rear = 0

포화 상태: (rear+1) mod n = front

 

포화 상태인 rear가 다음 위치를 찾을 때: (rear+1) mod n 

 -> front가 지나가 비어있는 0의 자리에 넣기 위해 자리를 찾을 때 쓴다.

 

연결리스트 큐

 

연결리스트 큐 

연결리스트로 표현된 큐에서는 front 포린터와 rear 포인터를 사용한다.

 

큐의 응용

1. 프린터 버퍼 큐 

 : 걍 프린트에서 활용 가능 (선입선출 특징)

2. 스케줄링 큐 

 : CPU사용 요청을 스케줄링함 (역시 선입선출)

3. 큐잉 시스템 

 : 시물레이션 시스템, 먼저 들어온 변수를 먼저 처리함 (ㅅㅇㅅㅊ)

 

 

데크 double-ended queue

큐 두 개를 각각 뒤집어서 합친 모양의 데크

데크 모습

양 쪽으로 insert/delete 가능 

문제점: insert/delete를 어디서 했는지 알 수 없음. 

해결책: 키워드를 붙인다. ex) insertFront / deleteFront

 

이중연결리스트 데크

데크가 양방향 연산이 가능하다는 점으로 이중연결리스트에서 이를 구현할 수 있다.

데크의 이중연결리스트

Llink와 Rlink를 이용한다. 

 

 

 

그림 출처 - 큐/원형큐: hellmath.tistory.com/ 연결리스트큐:songeunjung92.tistory.com/24

               데크: soft.plusblog.co.kr/24  

이중연결리스트데크:opentutorials.org/module/1335/8940