#23 [C 자료구조] 큐의 개념

큐는 이전에 언급했듯이 놀이공원에 줄서는 것과 같다고 볼 수 있다. 먼저 온 사람이 먼저 입장하고 나중에 온 사람은 늦게 들어가는 FIFO(First In First Out) 형식을 띈다.

자료구조에서는 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터를 출력하는 방식이라 생각하면 된다.

즉 스택과 다르게, 삽입은 큐의 제일 끝에서, 삭제는 큐의 제일 앞에서 일어나는 것이다.

큐가 삽입되고 삭제되는 과정

큐 사용 예시

• CPU의 태스크 스케쥴링
• 네트워크 프린터
• 실시간 시스템 인터럽트 처리
• 다양한 이벤트 구동 방식 컴퓨터 시뮬레이션
• 콜센터 전화 처리
• 이진 트리의 레벨 순화
• 그래프에서 너비 우선 탐색

큐의 구현 방법

큐의 구현 방법은 스택과 마찬가지로 배열과 연결리스트가 있다.

또한 마지막 데이터가 첫 데이터를 참조하는 원형 큐와 마지막 데이터가 참조하는 게 없는(끝인) 선형 큐로 나뉜다.

 

배열 선형 큐

큐 또한 미리 메모리를 할당해주는 정적 할당 방식을 먼저 코딩해보도록 하겠다.

 

- 큐를 만들고 맨 뒤에 item을 추가하는 코드

#define MAX_QUEUE_SIZE 100 // 큐 사이즈 메모리 정해주기

typedef struct {
	int key;
} element; //key 만들어가는 구조체를 만들어줌

element queue[MAX_QUEUE_SIZE]; //key 0~99까지 들어가는 큐 껍데기를 만들어줌

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

void addq(element item) //item을 큐 안에 추가해주는 식
{
	if ( rear == MAX_QUEUE_SIZE-1 ) {
          queueFull( );
          return;
	}
	queue[++rear] = item;
}

 

-item을 큐 앞쪽에서 빼주는 코드

element deleteq()
{
	if (front == rear)
    	return queueEmpty();
    return queue[++front];
}

 

그러나 선형 큐는 다음과 같은 크리티컬한 단점이 있다.

• 데이터 큐가 들어가고 나감에 따라 점차 오른쪽으로 이동핢
• 마지막에 가면 결국 rear 값이 최대치에 다다라서 포화 상태에 이르게 됨
• 따라서 왼쪽으로 데이터 이동이 필요한데, 이렇게 되면 시간 복잡도가 생기게됨!! (O(MAX_QUEUE_SIZE)

따라서 배열큐를 선형큐로 바꿔주는 작업이 필요하다.

if (rear == MAX_QUEUE_SIZE -1 )
	rear = 0;

요롷게 rear을 다시 저렇게 처음에 붙여주면된다!!

원형 큐에 대해서 조금 더 자세히 짚어보자

---

 

 

 

 

원형 큐(Circular Queue)

원형 큐는 일반 선형큐의 끝을 이어줘 논리적 원형 구조를 갖게 하는 방법이다.

초기 값: front == rear == 0 인 값이 된다!!

또한 데이터 수에 따라 front 와 rear 가 주기적을 변동한다.

따라서 삽입을 위해 rear은 항상 다음과 같이 위치를 확인해준다.

if (rear == MAX_QUEUE_SIZE -1)
	rear = 0;
else rear ++;

 

만약 원형 큐에서 데이터가 꽉찼으면 어떻게 할까?

1) Full이기 이전에 항상 데이터 한 칸을 비워두던가

2) Full이 되기 전에 동적 배열을 사용해 크기를 확장해주면 된다.

공백 상태와 포화 상태를 구별하기 위해 하나의 공간을 항상 비워준다!!

 

-rear가 front랑 같아 비어있는지 확인하고 아이템을 추가하는 코딩

void addq(element item) {
	rear = (rear + 1) % MAX_QUEUE_SIZE;
    if ( front == rear)
    	QueueFull(); //에러 호출
    queue[rear] = item;
}

-원형 큐에서 front 값 뽑아내는 코딩

element deleteq(){
	element item;
    if ( front == rear )
    	return queueEmpty(); // 지울 게 없다는 오류 호출
    front = (front + 1) % MAX_QUEUE_SIZE;
    return queue[front]; //front 값 호출 후 지워주기
}

 

다음 번엔 동적 할당 배열을 큐에 적용하는 법에 대해 서술해보겠다.

동적할당배열 지겨운 자식...