[자료구조] 큐(Queue) PART.1

1. 개념

• 데이터를 한쪽에서는 입력, 다른 한쪽에서는 출력하는 방식(First In First Out = FIFO)
• rear(tail) : 삽입 포인터
• front(head) : 삭제 포인터
• 큐의 단점은 한번 사용한 기억공간은 사용할 수 없다. 이 단점을 원형 큐로 보안
• 큐의 응용
   - 작업 스케줄링, 대기 큐, 스풀 운영에 사용

 

2. 구조

• 삽입은 뒤에서 일어난다.

삭제(out) ←	A	B	C	D		← 삽입(in)
	1	2	3	4	5
front(head)				rear(tail)

 

3. 연산 과정

1) 공백 큐 생성 : createQueue();

삭제(out) ←					← 삽입(in)
-1	1	2	3	4
front = rear

"front = rear"라는 것은 공백 상태를 말하고 둘 다 -1에 있으므로 초기 상태를 의미한다.

 

2) 원소 A 삽입 : enQueue(Q, A);

삭제(out) ←	A				← 삽입(in)
-1	1	2	3	4
front	rear

 

front와 rear이 같지 않으면 데이터가 있다는 것이다.

 

3) 원소 B 삽입 : enQueue(Q, B);

삭제(out) ←	A	B			← 삽입(in)
-1	1	2	3	4
front		rear

 

rear만 증가한다.

 

4) 원소 삭제

삭제(out) ←				← 삽입(in)
A	B
1	2	3	4
front	rear

 

frontr가 증가하면 삭제가 이루어진다는 것이다.

 

(1) 코드

 

deQueue(Q)
	if(isEmpty(Q)) then Queue_Empty();
	else{
		front <- front + 1
		return Q[front];
	}
end deQueue()

delete(Q)
	if(isEmpty(Q)) then Queue_Empty();
	else front <- front + 1;
end delete()

 

4. 데크(Deque)

• 양쪽 모두 삽입과 삭제를 할 수 있는 형태
• 스택과 큐의 장점만 따서 만든 복합체
• Double Ended Queue의 약자다.
• 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한(scroll)이 있다.
• 입력은 양쪽에서 일어나고 출력은 한 곳에서만 일어나는 출력 제한(shelf)이 있다.
• scroll : 입력 제한 데크
• shelf : 출력 제한 데크

1) 데크(Deque) 구조

(1) Scroll

삭제(out) ←	A	B	C		← 삽입(in) → 삭제(out)
	1	2	3	4	뒤

 

삭제가 앞, 뒤에서 일어나고 삽입은 원래 큐의 구조를 따른다.

 

(2) Shelf

삽입(in) → 삭제(out) ←	A	B	C		← 삽입(in)
	1	2	3	4	뒤

 

삽입이 앞, 뒤에서 일어나고 삭제는 원래 큐의 구조를 따른다.

 

 

5. 1차원 배열을 이용한 큐

• 큐의 크기 = 배열의 크기
   - 변수 front : 저장된 첫 번째 원소의 인덱스 저장
   - 변수 rear : 저장된 마지막 원소의 인덱스 저장
• 상태 표현
   - 초기 상태 : front = rear = -1
   - 공백 상태 : front = rear
   - 포화 상태 : rear = n - 1 (n : 배열의 크기, n - 1 : 배열의 마지막 인덱스)
• 초기 공백 큐 생성 알고리즘
   - 크기가 n인 1차원 배열 생성
   - front와 rear를 -1로 초기화
• 공백 큐 검사 알고리즘과 포화상태 검사 알고리즘
   - 공백 상태 : front = rear
   - 포화 상태 : rear = n - 1 (n : 배열의 크기, n - 1 : 배열의 마지막 인덱스)

1) 코드

(1) 초기 공백 큐 생성 알고리즘

 

createQueue()
	Q[n];

	front <- -1;
	rear <- -1;

end createQueue()

 

(2) 공백 큐 검사 알고리즘, 포화상태 검사 알고리즘

 

isEmpty(Q)
	if(front = rear) then return true;
	else return false;
end isEmpty()

isFull(Q)
	if(rear = n - 1) then return true;
	else return false;
end isFull()

 

2) 삭제 알고리즘

• 가장 앞에 있는 원소를 삭제해야 한다.

(1) 순서

1. front의 위치를 한 자리 뒤로 이동하여 큐에 남아있는 첫 번째 원소의 위치로 이동하여 삭제할 자리 준비
2. 그 자리의 원소를 삭제하여 반환

 

(2) 코드

 

deQueue(Q)
	if(isEmpty(Q)) then Queue_Empty();
	else {
		front <- front + 1;	// 1
		return Q[front];	// 2
	}
end deQueue()

delete(Q)
	if(isEmpty(Q)) then Queue_Empty();
	else front <- front + 1;
end delete()

 

6. 검색 알고리즘

• 가장 앞에 있는 원소를 검색하여 반환하는 연산

1) 순서

1. 현재 front의 한 자리 뒤(front + 1)에 있는 원소, 즉 큐에 있는 첫 번째 원소를 반환

 

peek(Q)
	if(isEmpty(Q)) then Queue_Empty();
	else return Q[front + 1];
end peek()

 

7. C언어 실습

 

#include <stdio.h>
#include <stdlib.h>
#define Q_SIZE 10

typedef char element;	// char형을 큐 element의 자료형으로 정의

typedef struct {	// 1차원 배열 큐 선언
	element queue[Q_SIZE];
	int front, rear;
}QUEUE;

QUEUE *createQueue() {	// 공백 큐를 생성하는 연산
	QUEUE *Q;
	Q = (QUEUE *)malloc(sizeof(QUEUE));
	Q -> front = -1;	// front 초깃값 설정
	Q -> rear = -1;	// rear 초깃값 설정
	return Q;
}

int isEmpty(QUEUE *Q) {	// 큐가 공백인지 확인하는 연산
	if (Q->front == Q->rear) {
		printf("\n Queue is empty.\n");
		return 1;
	}
	else return 0;
}

int isFull(QUEUE *Q) {	// 큐가 포화 상태인지 확인하는 연산
	if (Q->rear == Q_SIZE - 1) {
		printf("\n QUEUE is full.\n");
		return 1;
	}
	else return 0;
}

void enQueue(QUEUE *Q, element item) {	// 큐의 rear에 원소를 삽입하는 연산
	if (isFull(Q)) exit(1);
	else {
		Q -> rear++;
		Q -> queue[Q -> rear] = item;
	}
}

element deQueue(QUEUE *Q) {	// 큐의 front에서 원소를 삭제하고 반환하는 연산
	if (isEmpty(Q))	exit(1);
	else {
		Q -> front++;
		return Q -> queue[Q -> front];
	}
}

void del(QUEUE *Q) {	// 큐의 front에서 원소를 삭제하는 연산
	if (isEmpty(Q)) exit(1);
	else Q -> front++;
}

element peek(QUEUE *Q) {	// 큐의 가장 앞에 있는 원소를 검색하여 반환하는 연산
	if (isEmpty(Q)) exit(1);
	else return Q -> queue[Q -> front + 1];
}

void printQ(QUEUE *Q) {	// 큐의 내용을 출력하는 연산
	int i;
	printf(" Queue : [");
	for (i = Q -> front + 1; i <= Q -> rear; i++)
		printf("%3c", Q -> queue[i]);
	printf(" ] \n");
}

void main(void) {
	QUEUE *Q1 = createQueue();
	element data;
	printf(" 삽입 A --> ");	enQueue(Q1, 'A');	printQ(Q1);
	printf(" 삽입 B --> ");	enQueue(Q1, 'B');	printQ(Q1);
	printf(" 삭제 -->");	deQueue(Q1);	printQ(Q1);
	printf(" 삽입 C --> ");	enQueue(Q1, 'C');	printQ(Q1);
	data = peek(Q1); printf(" peek item : %c \n", data);
	printf(" 삭제 -->");	deQueue(Q1);	printQ(Q1);
	printf(" 삭제 -->");	deQueue(Q1);	printQ(Q1);
}

 

 

큐(Queue) 실행