큐(Queue)

큐의 정의

  - 선형리스트에서 한쪽에서는 삽입연산이 반대쪽에서는 삭제 연산이 이루어지도록 한 것.

  - 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 성질을 갖는다. < FIFO(First-In-First-Out) >

- rear : 큐에서 데이터의 삽입이 이루어지는 쪽, 가장 최근에 삽입된 데이터의 위치를 가리킴.   - front : 큐에서 데이터의 삭제가 이루어지는 쪽, 가장 최근에 삭제된 데이터의 위치를 가리킴.

 

큐의 기본 연산 

 

큐의 생성

#define QUEUE_SIZE 100 typedef struct {     char *item1[20]     int item2;     ··············· }Element;   Element queue[QUEUE_SIZE]; int rear = -1;     // 최초 생선된 큐는 공백 상태이므로 rear = -1 int front = -1;    // 최초 생선된 큐는 공백 상태이므로 front = -1

 

큐의 포화/공백 상태 검사 함수 

bool IsFull(int rear) {     if(rear == QUEUE_SIZE -1) return true;    //포화상태     else return false; }   bool IsEmpty(int front, int rear) {     if(front == rear) return true;    //공백 큐 상태     else return false;                // 공백이 아닌 큐 상태 }

 

큐의 삽입/삭제 함수

void Enqueue(int *rear, Element item)    //삽입 {     if(IsFull(*rear))    //큐의 포화상태 검사     {         queue_full();    // 포화 상태인 경우         return;     }     queue[++(*rear)] = item;    // rear의 값을 증가시킨 후 item 삽입 }   Element Dequeue(int *front, int rear)    //삭제 {     if(IsEmpty(*front, rear))    //큐의 공백 상태 검사     {         return queue_empty();    //공백 상태인 경우 오류 키 반환     }     return queue[++(*front)];    //front값을 증가 후 반환 }