큐 (Queue)

큐(Queue)

 

FIFO

 

[개념] 먼저 넣은 데이터가 먼저 나오는 선입선출 구조

[유형] 선형큐 - 배열을 선형으로 사용하여 큐 구현. 문제점 많아 미사용

순환큐 - 배열의 끝과 시작이 이어진 것처럼 전단과 후단을 관리

링크드 리스트 기반 큐 - 성능은 떨어지나 공백/포화 상태 관리가 필요없음

[문제점/해결방안]

1. 삽입삭제 인덱스 사용

2. 순환큐 사용

3. 링크드 리스트 사용

 

#define MAX_SIZE 100

typeof struct{ int key; } element; element queue[MAX_SIZE];

int rear=-1; int front=-1;

element dequeue(int *front, int rear){

if(*front==rear){printf("Queue empty"); return 0;}

else{ return queue[++*front];}}

 

void enqueue(int *rear, element item){

 if(*rear== MAX_SIZE-1){printf("Queue full"); retrun; }

 queue[++*rear]=item; }

 

우선순위 큐(Priority Queue)

 

not FIFO, 스택/큐로 구현가능

최소 우선순위 큐/최대 우선순위 큐

 

[개념] 보통의 큐처럼 동작하지만 우선순위 속성을 갖는 데이터를 처리

[연산] 

1)삽입 - 우선순위 큐에 요소를 추가

2)삭제 - 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환

 

 

순환큐(Circular Queue)

 

front, rear, 선형큐 문제 해결

 

[개념] 1차원 배열을 사용하여 순차 자료구조 방식으로 큐를 구현

더미 공간을 생성하여 원래 용량(capacity)보다 +1 만큼 증가시켜 배열을 생성

[연산] 1)삽입 - Rear쪽 삽입. 포인터 이동 2)삭제 - Front 삭제. 포인터 이동

 

Rear == Front'는 비어있는 상태

'Rear + 1 == Front' 는 가득찬 상태