배열을 이용한 큐queue 의 구현

4. 배열을 이용한 큐의 구현

큐의 생성

- 변수 rear의 초기값은 큐의 공백 상태를 나타내는 ‘­1’로 시작함

#define QUEUE_SIZE 5
typedef int element;
element queue[QUEUE_SIZE];
	int front = -1;
	int rear = -1;

큐의 삽입 연산

- 삽입 연산이 발생하면 rear변수만 오른쪽으로 이동하고,

  삭제 연산이 발생하면 front변수만 오른쪽으로 이동함

 

void Add_q(int *rear, element item) {
if (*rear == QUEUE_SIZE-1) {
	printf(“Queue is full !!”);
	return; 	}
queue[++(*rear)] = item;
return; 	}

 

 

큐의 삭제 연산

- 삭제 연산의 수행 결과로 삭제된 원소를 Delete_q 연산자의 호출 프로그램에게 반환해 줌

 

element Delete_q(int *front, int rear) {
  if (*front == rear) {
	printf("Queue is empty\n");
	return;  }
  return ( queue[++(*front)] );  }

 

 

 

 

5. 원형 큐

큐의 만원 상태

원형 큐의 초기 상태

- 배열의 문제점을 해결하기 위해 원형 큐가 제안됨

- 원형 큐는 파이프의 입구와 출구 부분을 연결시킨 형태

 

원형 큐의 삽입 연산 결과

 

정리하기

1. 큐는 한쪽에서는 삽입이 발생하고 다른 한쪽에서는 삭제가 발생하도록 정의되었으며, 먼저 삽입된 원소가 먼저 삭제되므로 선입 선출(First-In-First-Out : FIFO) 또는 선착순 서브(First-Come-First-Serve : FCFS) 알고리즘을 갖는 순서 리스트라고 합니다.

 

2. 큐에서는 원소의 삭제연산이 이루어지는 곳을 앞(front)이라 하고 삽입연산이 이루어지는 곳을 뒤(rear)라고 합니다.

 

3. 큐 생성 함수(Create_q(maxQueueSize))를 호출하기만 하면 프로그래머가 지정한 크기의 새로운 큐를 생성할 수 있습니다. Create_q(maxQueueSize) 함수의 매개변수인 maxQueueSize는 큐가 저장할 수 있는 최대 개수의 원소(element)를 의미합니다.

 

4. Boolean IsFull_q(queue, maxQueueSize) 연산은 큐가 가득 찼는지를 확인합니다. 즉, 큐에 저장된 원소(element)의 개수가 maxQueueSize와 같다면, 그 큐는 가득 찼으며 큐에 자료(원소)를 더 이상 저장시킬 수 없다는 것을 의미합니다.

 

5. Queue Add_q(queue, item) 연산은 큐에 새로운 원소를 삽입합니다. 만일 큐가 가득 찼다(Full)면 더 이상의 원소를 큐에 삽입할 수 없으며, ‘queueFull‘ 메시지를 출력합니다.

 

6. Boolean IsEmpty(queue) 연산은 큐 상태가 빈 상태인지를 확인합니다. 만일 큐가 빈 상태이면 ‘TRUE’ 값을 반환하고, 큐에 하나이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.

 

7. Element Delete_q(queue) 연산자는 큐가 빈 상태라면 삭제할 원소가 없으므로 ‘queueEmpty‘를 출력합니다. 하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 큐의 front가 가리키는 원소를 삭제하고 그 원소를 반환합니다.

 

8. 큐의 추상자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.

 

9. 원형큐는 파이프의 입구와 출구 부분을 연결시킨 형태입니다. 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 ‘나머지 연산자‘를 사용합니다.