[자료구조] 큐

 

 

1. 큐: 입력된 순서대로 순차적으로 처리되기 위해 기다리는 자료들의 모음 (영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말함)

 

 - 선입선출 (FIFO : First-In First-Out) 방식

  먼저 들어 온 데이터가 먼저 나오는 구조 (스택의 (LIFO : Last-In First-Out)와 반대되는 개념)

  스택과 달리 큐는 한쪽 끝에서 데이터 삽입 작업이 이루어지고, 반대쪽 끝에서는 데이터 삭제 작업이 이루지는 리스트

 

 

 

 

 

2. 큐 관련 포인터 

 - 기본적으로 첫 원소와 마지막 원소를 각각 가리키는 두개의 포인터(인덱스)를 사용 (예) front/rear

 - 실전에서는 front는 첫 원소가 아닌 바로 그 앞을 가리키도록 설정 -> front = rear 이면, 큐가 비어있음을 의미

 

 

 

 

 

3. 큐 관련 주요 연산/함수

  • createQueue() ::= 새로운 큐를 생성한다.

  • is_empty(q) ::= 큐 q가 비어있는지를 검사한다.

  • is_full(q) ::= 큐 q가 가득 찼는지를 검사한다.

  • enQueue(q, e) ::= 큐 q의 맨 뒤에 요소 e를 추가한다.

  • deQueue(q) ::= 큐 q의 맨 처음에 있는 요소를 삭제한다.

  •peek(q) ::= 큐 q의 맨 처음에 있는 요소를 삭제하지 않고 반환한다

 

 

 

 

* 스택과 큐에서의 삽입/삭제 연산 비교

 

 

 

 

4. 큐의 용도 

- FIFO 성질 이용

  • 운영체제의 작업 스케쥴링 (우선순위 지정 => 성능 강화)

  • 공유 프린터 작업 스케쥴링 및 버퍼(임시 저장)

  • 데이터 통신/네트워크 등

  • 각종 시뮬레이션 (대기열 처리, 큐잉 이론)

 

 

 

 

 

5. 큐의 연산 과정

* front는 보통 첫 원소가 들어있는 인덱스 보다 1 작은 값을 가지도록 설정

* rear는 마지막 원소의 인덱스를 가지도록 설정

 

* 큐의 크기 = 배열의 크기, n

 - 상태 표현

   초기 상태 : front = rear = -1

   공백 상태 : front = rear

   포화 상태 : rear = n-1 

  (n : 배열의 크기)

 

* front와 rear가 다시 같아짐 => 초기상태와 같이 큐가 비었음을 의미

 

 

①공백 큐 생성 : createQueue();

 

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

 

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

 

④원소 삭제 : deQueue(Q);

 

 

 

6. 큐 프로그램 구현 (단순 배열)

// 큐가 하나인 경우, 단순화 가능

#define MAX_Q_SIZE 100
typedef int element; 
element Queue[MAX_Q_SIZE]; 
int front, rear; 
// 큐 초기화 함수 
void init() 
{ 
     front = rear = -1; 
} 
// 공백 상태 검출 함수 
int is_empty() 
{ 
     return (front == rear); 
} 
// 포화 상태 검출 함수 
int is_full() 
{ 
     return (rear == (MAX_Q_SIZE - 1)); 
}

// 삽입함수
//큐가 꽉 찼으면 오류 발생
// rear가 가리키는 원소 다음에 새로운 값 삽입(rear 증가시킨 후, rear가 가르키는 원소 자리에 삽입)
void enQueue(element item) 
{  
      if( is_full() ) { 
             cout << “큐 포화 에러\n”; 
             return;                
       } 
       else Queue[++rear] = item; 
} 


// 삭제함수 
//큐가 비어있으면 오류 발생
//front를 먼저 증가시킨 후, 증가된 front가 가리키는 원소를 반납
element deQueue() 
{  
    if( is_empty() ) { 
             cout << “큐 공백 에러\n”; 
             exit(1);               
     } 
     else return Queue[++front]; 
}  


// 피크함수 
element peek() 
{ 
    if( is_empty() ) { 
             cout << “큐 공백 에러\n”; 
             exit(1);               
     } 
     else return Queue[front]; 
}

 

 

 

7. 큐의 구현 (연결리스트)

  - 배열 대신 연결리스트로 원소들을 관리

     • 큐의 원소 : 단순 연결 리스트의 노드

     • 큐의 원소의 순서 : 노드의 링크 포인터로 연결

     • 변수 front : 첫 번째 노드를 가리키는 포인터 변수 (초기 null)

     • 변수 rear : 마지막 노드를 가리키는 포인터 변수 (초기 null)

 

 

  - 주요 특징

     • 배열을 이용할 경우에 비해, 크기 제한이 거의 없음

     • 동적 메모리 할당으로 기억장소 사용에 제한이 적음

     • 큐에서 enQueue 및 deQueue 방법은 단순연결리스트의 삽입/삭제 방법과 거의 동일

     • 배열의 인덱스 대신 포인터 사용에 따른 부담은 존재

    

 

 

 

 

8. 연결리스트 큐의 특징

  - 큐의 상태

     • 초기 상태 : front = rear = null

     • 공백 상태 : front = rear = null

        -> 초기 상태와 공백 상태가 동일!

       + 큐가 꽉 차서 더 이상의 원소를 추가하지 못하는 경우는 거의 없음.

 

 

 

 

 

9. 연결리스트 큐의 연산

 

1) EnQueue

① 삽입할 새 노드를 생성.

  삽입할 새 노드는 연결 큐의 마지막 노드가 되어야 하므로 링크 필드에 null을 저장한다.

 

② 새 노드를 삽입하기 전에 연결 큐가 공백인지 아닌지를 검사한다. 연결 큐가 공백인 경우에는 삽입할 새 노드가 큐의 첫 번째 노드이자 마지막 노드이므로 포인터 front와 rear가 모두 새 노드를 가리키도록 설정한다.

 

 

 

③ 큐가 공백이 아닌 경우, 즉 노드가 있는 경우에는 현재 큐의 마지막 노드의 뒤에 새 노드를 삽입하고 마지막 노드를 가리키는 rear가 삽입한 새 노드를 가리키도록 설정한다.

 

 

 

 

2) DeQueue

① 삭제연산에서 삭제할 노드는 항상 큐의 첫 번째 노드로서 포인터 front가 가리키고 있는 노드이다. front가 가리키는 노드를 포인터 old가 가리키게 하여 삭제할 노드를 지정한다.

 

 

② 삭제연산 후에는 현재 front 노드의 다음 노드가 front 노드(첫번째 노드)가 되어야하므로, 포인터 front를 재설정한다.

 

 

③ 큐에 노드가 하나뿐이어서 삭제 연산 후에 공백 큐가 되는 경우 검사:

    -> 큐의 마지막 노드가 없어지므로 포인터 rear도 null로 설정한다. 

 

 

④ 포인터 old가 가리키고 있는 노드를 삭제하고, 메모리 공간을 시스템에 반환(free() 함수)한다

 

 

 

 

 

10. 큐 프로그램 구현 (연결리스트)

// 단일 연결리스트 큐를 사용
typedef char element; 

class QNode{ 
    element data; 
    QNode *link; 
}; 
  
Qnode *front, *rear; 
// 큐 초기화 함수 
void init() 
{   
     front = rear = NULL; 
} 

// 공백 상태 검출 함수 
int is_empty() 
{   
     return (front == NULL); // front가 NULL이면 rear도 NULL;
} 




void enQueue(element item) 
{   // 새 노드를 할당받음
    QNode *newNode = new QNode; 
    newNode->data = item; 
    newNode->link = NULL;
 
    // 새 노드를 리스트에 추가
    if(front == NULL) { // 큐가 비어 있으면
	front = newNode; 
   	rear = newNode;        
    } 
    else { 
        rear->link = newNode; 
        rear = newNode; 
    }     
} 

element deQueue() 
{     QNode *old = front; 
      element item; 

      if (is_empty()) return 0; // 또는 오류 처리
      else { 
           item = front->data; 
           front = front->link; 
           if(front == NULL) rear = NULL; 
        
           return item; 
       } 
}