자료구조 정리) 큐

큐는 선입 선출 FIFO FIrst In First Out

큐의 삽입이 일어나는 곳을 후단(rear)

큐의 삭제가 일어나는 곳을 전단(front)

삽입 연산인 enqueue

삭제 연산인 dequeue

삽입 삭제 관리를 위해 스택에서는 top이라는 변수를 사용한다면,

큐에서는 rear와 front 2개의 변수를 사용한다.

1) 선형큐 (배열로 구현된 큐)

• front와 rear의 초기값은 -1
• 데이터 증가시 : rear++, 그 자리에 데이터가 저장된다
• 데이터 삭제시: front ++, 그자리에 있는 데이터를 삭제 

단점: 

언젠가는 배열의 끝에 도달하게 되어서, 배열의 앞부분이 비어있어도 사용하지 못한다는 점

따라서 주기적으로 모든요소를 왼쪽으로 옮겨야한다.

2) 원형 큐 

특징: front와 rear값이 배열에 끝에 도달하게 되면 다음에 증가되는 값은 0 이 되도록 하는 것이다.

• front 와 rear 초기값은 0 ( front는 큐의 첫번째 요소 하나 앞 ,rear는 마지막 요소를 가리킨다)

삽입시: rear ++, 그 위치에 새로운 데이터가 삽입

삭제시: front++, 그 위치에서 데이터 삭제 

• front와 rear값이 같으면 원형 큐가 비어있음
• 원형큐에서는 포화 상태랑 공백 상태를 구별하기 위해 하나의 자리를 항상 비워둔다. 그래서 front가 rear보다 하나 앞에 있으면 포화상태이다.
• ( 이 부분은 count를 사용하면 하나의 자리를 비워두지 않아도 된다.)

삽입 삭제시

front= (front+1) % SIZE

rear= (rear+1) % SIZE

if(front==(rear+1) % SIZE) => 포화 상태

3) 연결 리스트 큐 

특징: 배열 큐에 비해 사이즈가 제한이 없다는 점

단점: 코드가 복잡하고 링크 필드 때문에 메모리 공간을 더 많이 사용한다.

front는 연결리스트 맨 앞에 있는 요소를 가리킨다

rear 포인터는 맨 뒤에 있는 요소를 가리킨다 

삽입

1)큐가 공백 상태라면 front =rear= NULL

 front, rear 모두 새로운 노드를 가리키게 한다

2)기존에 공백 상태가 아니라면 

rear가 가리키고 있는 노드의 링크필드가 새로운 노드를 가리키게

rear가 새로운 노드를 가리키도록 

void enqueue( QueuType * q, element item)
{
    QueuNode * temp= (QueueNode *) malloc (sizeof(QueueNode));
    if(temp==NULL) 
    {
        // 메모리를 할당 할 수 없음 
    }
    else
    {
        temp-> item= item;
        temp-> link = NULL:
        if(is_empty(q)) // 큐가 공백 상태라면 초기에 front, rear 할당 해줌
        {
            q->front= temp; 
            q->rear= temp;
        }    
        else
        {
            q->rear-> link= temp; // rear가 가리키던 노드와 새 노드를 연결해주고
            q->rear= temp; // rear를 새로운 노드를 가리키게 이동 
        }
    }
}

삭제

1. 연결리스트의 처음에서 노드를 꺼내온다.

2. 먼저 공백 상태인지를 검사하여야 한다.

1) 공백이면 삭제할 수 없어서 error

2) 공백이 아니라면 삭제 진행

front가 가리키는 노드를 temp가 가리키게 하고 (temp= front)

front가 front의 link 를 가리키게 변경 

temp를 동적 해제 

element dequeue( QueType * q)
{
    QueueNode * temp= q->front; // temp= front. front값 접근하려고 
    element item;
    if( is_empty(q))
    {
        // 큐가 비어 있으면 끝
    }
    else
    {
        item= temp-> item;  
        q->front= q->front->link; // 큐의 front 값을 그 다음 것을 가리키도록 
        free(temp);
        if(q->front== NULL) //만일 front가 처음으로 돌아왔다면
            q->rear= NULL; //후단을 아무것도 안가리키는 NULL로 처리
        free(temp);
        return item;
    }
 
    
 
}