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;
원형큐의 구현
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;
덱의 구현
'대학교 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 |