[자료구조] Queue

오늘은 큐에 대해서 공부해보려고 합니다.

 

큐는 앞에서 살펴본 스택과는 달리 삽입과 삭제가 다른 방향으로 나오는 형태의 리스트를 뜻합니다. 먼저 삽입된 데이터가 먼저 나오는 형태입니다. 이 때문에 First-In-First-Out (FIFO) list라고도 부릅니다. 

 

스택에서는 top을 이용해서 배열을 관리하는 것처럼, 큐에서는 front, rear 두 개의 변수를 이용합니다. front는 큐의 앞 쪽 끝을 가리키고, rear는 큐의 제일 뒤 쪽 끝을 가리키게 됩니다. 기본적인 형태는 다음과 같습니다.

 

 

front와 rear는 -1로 초기화하여 선언합니다. 데이터가 추가될 때마다 제일 뒤를 가리키는 변수인 rear가 1씩 증가하고, 데이터가 삭제될 때마다 가장 앞을 가리키는 변수인 front가 1씩 증가합니다. 

 

---

큐를 C를 이용하여 구현하면 다음과 같이 구현할 수 있습니다. 

 

#define MAX_QUEUE_SIZE 100

typedef struct {

      int key;

} element;



element queue [MAX_QUEUE_SIZE];

int rear = -1;

int front = -1;

 

큐에 데이터를 추가하는 함수는 다음과 같이 구현이 가능합니다.

 

void addq (element item) {

      if (rear == MAX_QUEUE_SIZE-1) // rear가 큐의 최대 사이즈에 도달하면

            printf("Queue is Full\n");      

      queue [++rear] = item;       

}

 

rear 값을 1 증가시킨 뒤 큐의 rear의 위치에 데이터를 집어 넣어 줍니다.

 

큐에서 데이터를 삭제하는 함수는 다음과 같이 구현이 가능합니다.

 

element deleteq () {

      if (front == rear)  // front와 rear의 값이 같다는 말은 큐가 비어있다는 것을 뜻합니다.

             printf("Queue is Empty\n");

      return queue [++front];

}

 

데이터를 삭제할 때는 front에 1을 추가시킨 뒤 큐의 front 위치의 데이터를 리턴 시켜줍니다.

 

 

이번 글에서는 큐의 대략적인 개념에 대해 알아보았습니다. 다음 글에서 큐의 조금 더 발전된 버전인 Circular Queue (원형 큐)에 대하여 알아보도록 하겠습니다. 읽어주셔서 감사합니다.