[Data Structures & Algorithms] 큐(Queue)의 이해와 알고리즘 (연결 큐, 순차 큐, 원형 큐)

🦄 큐(Queue)란?

큐(Queue)는 데이터의 삽입과 삭제가 각각 다른 끝에서 이루어지는 선형 자료구조로, "선입선출(FIFO, First-In-First-Out)" 원칙을 따른다.

스택과 마찬가지고 삽입과 삭제 위치가 제한되어 있으며 뒷 부분에서는 삽입만을, 앞 부분에서는 삭제 작업만을 수행할 수 있는 구조를 가진다.

 

---

 

💜 큐(Queue)와 스택

연산 항목	삽입 연산		삭제 연산
자료구조	연산자	삽입 위치	연산자	삭제 위치
Stack	push	top	pop	top
Queue	enQueue	rear	deQueue	front

 

---

 

💜 큐(Queue)의 추상 자료형

ADT Queue

    //공백 큐 생성
    createQueue() ::= create an empty Q;
    
    //큐가 공백 상태인지 검사
    isEmpty(Q) ::= if (Q is empty) then return true
                   else return false;
    
    //큐의 rear에 원소 삽입
    enQueue(Q, item) ::= insert item at the rear of Q;
    
    //큐의 front에 있는 원소 삭제
    deQueue(Q) ::= if (isEmpty(Q)) then return error
                   else
                   {
                       delete and return the front item Q
                   };
                   
    //큐의 front에 있는 원소 반환
    peek(Q) ::= if (isEmpty(Q)) then return error
                else
                {
                    return the front item of the Q
                };
     
End Queue

 

---

 

🦄 순차 큐(Queue)의 구현과 알고리즘

💜 순차 자료구조를 이용한 순차 큐(Queue)의 구현

ⓐ 1차원 배열을 이용한 큐

• 큐의 크기  ==  배열 크기
• 변수 front  ==  저장된 첫 번째 원소의 인덱스
• 변수 rear  ==  저장된 마지막 원소의 인덱스

 

ⓑ 상태 표현

• front의 초기 상태  ==  rear의 초기 상태  ==  - 1
• 공백 상태일 때는 front  ==  rear
• rear  ==  n - 1 이라면 포화 상태

 

---

 

💜 순차 큐(Queue) 생성 알고리즘

① 순차 큐(Queue) 생성 알고리즘

createQueue()

    Q[n]; //크기가 n인 1차원 배열 생성
    front <- - 1; //front의 크기를 -1로 초기화
    rear <- - 1; //rear의 크기를 -1로 초기화
    
end createQueue()

 

 

② 순차 큐(Queue) 공백 상태검사 알고리즘

isEmpty(Q)

    if (front == rear) //rear값과 front값이 같으면 공백 상태
    {
        return true;
    }
    else
    {
        return false;
    }
    
end isEnpty()

 

 

③ 순차 큐(Queue) 포화 상태검사 알고리즘

isFull(Q)

    if (n - 1 == rear)
    {
        return true; //포화 상태
    }
    else
    {
        return false;
    }
    
end isFull()

 

 

④ 순차 큐(Queue) 삽입 알고리즘

enQueue(Q, item)

    if (isFull(Q))
    {
        Queue_Full(); //큐가 포화 상태일 경우 삽입 불가
    }
    else
    {
        rear <- rear + 1; //마지막 원소의 인덱스를 저장한 rear 값 1 증가
        Q[rear] <- item; //수정된 rear값에 해당하는 원소에 item 저장
    }
    
end enQueue()

 

 

⑤ 순차 큐(Queue) 삭제 알고리즘

deQueue(Q)

    if (isEmpty(Q))
    {
        Queue_Empty(); //큐가 공백 상태일 경우 삭제 불가
    }
    else
    {
        front <- front + 1; //front의 위치를 한 자리 뒤로 이동
        return Q[front]; //front 자리의 원소를 삭제 후 반환
    }
    
end deQueue()

 

 

⑥ 순차 큐(Queue) 검색 알고리즘

peek(Q)

    if (isEmpty(Q))
    {
        Queue_Empty(); //큐가 공백 상태일 경우 검색 불가
    }
    else
    {
        return Q[front + 1]; //큐에 있는 첫 번째 원소 반환
    }
    
end peek()

 

---

 

🦄 원형 큐의 구현과 원형 큐 알고리즘

💜 원형 큐(Queue)의 구현

① 초기 공백 상태

• front = rear = 0

② 순차 큐와 원형 큐의 비교

종류	삽입 위치	삭제 위치
순차 큐	rear = rear + 1	front = front + 1
원형 큐	rear = ( rear + 1 ) mod n	front = ( front + 1 ) mod n

 

③ 사용 조건

• 공백 상태와 포화 상태 구분을 위해 front가 있는 자리는 항상 공란으로 둔다.

 

---

 

💜 원형 큐(Queue) 생성 알고리즘

① 원형 큐(Queue) 생성 알고리즘

createQueue()

    cQ[n]; //크기가 n인 1차원 배열 생성
    front <- 0; //front의 크기를 0으로 초기화
    rear <- 0; //rear의 크기를 0으로 초기화
    
end createQueue()

 

 

② 원형 큐의 공백 상태 검사 알고리즘

isEmpty(Q)

    if (front == rear) //rear값과 front값이 같으면 공백 상태
    {
        return true;
    }
    else
    {
        return false;
    }
    
end isEnpty()

 

 

③ 원형 큐의 포화 상태 검사 알고리즘

isFull(Q)

    if (((rear + 1) mod n) == front)
    {
        return true; //포화 상태
    }
    else
    {
        return false;
    }
    
end isFull()

 

 

④ 원형 큐(Queue) 삽입 알고리즘

enQueue(cQ, item)

    if (isFull(cQ))
    {
        Queue_Full(); //큐가 포화 상태일 경우 삽입 불가
    }
    else
    {
        rear <- (rear + 1) mod n;
        cQ[rear] <- item;
    }
    
end enQueue()

 

 

⑤ 원형 큐(Queue) 삭제 알고리즘

deQueue(cQ)

    if (isEmpty(cQ))
    {
        Queue_Empty(); //큐가 공백 상태일 경우 삭제 불가
    }
    else
    {
        front <- (front + 1) mod n;
        return cQ[front];
    }
    
end deQueue()

 

---

 

🦄 연결 큐(Queue)의 구현과 알고리즘

💜 연결 자료구조를 이용한 연결 큐(Queue)의 구현

① 연결 큐

: 단순 연결 리스트를 이용한 큐

• 큐의 원소 = 단순 연결 리스트의 노드
• 큐의 원소의 순서 = 노드의 링크 포인터로 연결
• 변수 front = 첫 번째 노드를 가리키는 포인터 변수
• 변수 rear = 마지막 노드를 가리키는 포인터 변수

 

② 포화 상태와 초기 상태 표현

• rear = front = null

 

---

 

💜 연결 큐(Queue)와 알고리즘

① 연결 큐(Queue) 생성 알고리즘

createLinkedQueue()

    front <- NULL;
    rear <- NULL;
    
end createLinkedQueue()

 

 

② 연결 큐(Queue) 공백 상태검사 알고리즘

isEmpty(LQ)

    if (front == NULL) //공백 상태
    {
        return true;
    }
    else
    {
        return false;
    }
    
end isEnpty()

 

 

③ 연결 큐(Queue) 삽입 알고리즘

enQueue(LQ, item)

    new <- getNode();
    new.data <- item; //데이터 필드에 item 저장
    new.link <- NULL; //삽입할 새 노드는 연결 큐의 마지막 노드가 되어야 함
    
    if (front == NULL) //큐가 공백 상태인 경우
    {
        //포인터 rear과 front가 모두 새 노드를 가리키도록 설정
        rear <- new;
        front <- new;
    }
    else //큐가 공백 상태가 아닌 경우
    {
        rear.link <- new;
        rear <- new;
    }
    
end enQueue()

 

 

④ 연결 큐(Queue) 삭제 알고리즘

deQueue(LQ)

    if (isEmpty(LQ))
    {
        Queue_Empty(); //큐가 공백 상태일 경우 삭제 불가
    }
    else
    {
        old <- front;
        item <- front.data;
        front <- front.link;
        
        if (isEmpty(LQ))
        {
            rear <- NULL;
        }
        
        returnNode(old); //포인터 old가 가리키고 있는 노드 삭제 후 메모리 공간 반환
        return item;
    }
    
end deQueue()

 

 

⑤ 연결 큐(Queue) 검색 알고리즘

peek(LQ)

    if (isEmpty(LQ))
    {
        Queue_Empty(); //큐가 공백 상태일 경우 검색 불가
    }
    else
    {
        return (front.data); //연결 큐의 첫 번째 노드의 데이터 필드값 반환
    }
    
end peek()