큐 자료 구조 특징 | 큐의 수도 알고리즘 Pseudo Algorithm of Queue

1. 큐 Queue

출처 : 나무위키

큐는 대기 줄과 같은 자료구조입니다.

 

은행에서 방금 도착했다면, 가장 나중으로 대기 순번이 정해집니다. 그리고 은행 창구에서는 가장 빨리 온 사람들을 먼저 부르게 됩니다.

즉, 먼저 들어온 데이터가 먼저 나가는 선입선출, FIFO, First In First Out 방식입니다.

 

1. 1. 가능한 작업

 

• Enqueue: 데이터를 큐의 뒤쪽(rear)에 삽입합니다.
• Dequeue: 데이터를 큐의 앞쪽(front)에서 삭제합니다.

 

1. 2. 활용

 

• 프린터 스풀러: 여러 작업이 프린터에 보내질 때, 작업들은 큐에 저장됩니다. 프린터는 큐에서 하나씩 작업을 꺼내어 인쇄합니다.
• 프로세스 관리: 운영체제는 프로세스의 상태를 관리하기 위해 큐를 사용합니다. 예를 들어, 준비 상태의 프로세스를 관리하는 준비 큐, 입출력 요청을 대기하는 프로세스를 관리하는 대기 큐가 있습니다.
• 데이터 스트림 처리: 네트워크 패킷 처리, 메시지 큐 등의 데이터 스트림에서 데이터가 도착한 순서대로 처리됩니다.
• 시뮬레이션: 은행 업무 처리, 차량 대기열 등 다양한 시뮬레이션 모델에서 큐가 사용됩니다.

2. 큐의 삽입 알고리즘 Enqueue

큐 자료구조에 데이터를 삽입할 때는, 데이터는 큐의 가장 뒤쪽에 추가됩니다.

Procedure Enqueue(Data)
    if Rear >= n then
        call Queue-Full
    else
        Rear = Rear + 1
        Queue(Rear) = Data
end Procedure

 

 

 

 

• n : 큐의 최대 크기
• Rear : 큐의 마지막 요소의 인덱스

 

Data를 Queue에 삽입하는 Enqueue 작업을 수행합니다.

만약 큐의 최대 크기인 n보다 큐의 마지막 요소의 인덱스인 Rear 크거나 같다면,

큐가 꽉 찬 상태임을 의미하고, Queue-Full 함수를 호출합니다.

그렇지 않다면, Rear을 뒤로 한 칸 보내고, 뒤로 보낸 Rear에 새로운 데이터를 삽입합니다.

 

3. 큐의 삭제 알고리즘 Dequeue

큐 자료구조에 데이터를 삭제할 때는, 가장 앞쪽(front)에 있는 데이터가 삭제됩니다.

Procedure Dequeue
    if Front = Rear then
        call Queue-Empty
    else
        Front = Front + 1
        Remove Queue(Front)
end Procedure

 

• Front : 큐의 첫 번째 요소의 인덱스
• Rear : 큐의 마지막 요소의 인덱스

Data를 Queue에서 삭제하는 Dequeue 작업을 수행합니다.

만약 큐의 첫 번째 요소의 인덱스인 Front가 마지막 요소의 인덱스인 Rear와 같다면,

큐가 비어 있는 상태임을 의미하고, Queue-Empty 함수를 호출합니다.

그렇지 않다면, Front를 앞으로 한 칸 보내고, 앞으로 보낸 Front 위치의 데이터를 삭제합니다.