자료구조

[자료구조] 큐(Queue)

Seunghyun_KO 2022. 1. 9. 09:00
728x90
반응형

큐 (Queue)

 - 스택과 마찬가지로 삽입삭제의 위치가 제한된 유한 순서 리스트

 - 선입선출 구조(FIFO, First-In-First-Out) : 삽입 순으로 나열되어 가장 먼저 삽입한 원소가 가장 먼저 삭제된다.

삭제
         front                                                                  rear         삽입


큐의 연산 과정

 - 삽입 : enQueue

더보기

① 공백 큐 생성 : 큐가 생성되지 않은 최초 상태에서만 실행

Q [0] [1] [2]
     
 ↑ front == rear == -1 ↑   

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

Q [0] [1] [2]
             A                 
 ↑ front == -1 ↑   ↑ rear == 0 ↑     

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

Q [0] [1] [2]
A              B               
 ↑ front == -1 ↑     ↑ rear == 1 ↑   

 

 - 삭제 : deQueue

더보기

초기 상태

Q [0] [1] [2]
A              B               
 ↑ front == -1 ↑     ↑ rear == 1 ↑   

① 원소 삭제 : deQueue(Q);

Q [0] [1] [2]
 A  B  
   ↑ front == 0 ↑   ↑ rear == 1 ↑   

 

 - 스택(stack)과 큐(queue)의 연산 비교

                       항목

자료구조
삽입 삭제
연산자 삽입 위치 연산자 삭제 위치
스택 (stack) push top pop top
큐 (queue) enQueue rear deQueue front

선형 큐

 - 1차원 배열을 이용한 큐

    ㄴ 큐의 크기 = 배열의 크기

    ㄴ 변수 front : 저장된 첫 번째 원소의 인덱스

    ㄴ 변수 rear : 저장된 마지막 원소의 인덱스

 - 상태 표현

    ㄴ 초기 : front == rear == -1

    ㄴ 공백 : front == rear

    ㄴ 포화 : rear == n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)

 - 선형 큐의 문제점 : 선형 큐의 잘못된 포화상태 인식

선형 큐에서 삽입과 삭제의 반복 시 front가 뒤로 계속 밀리면서 자리가 있음에도 불구, 포화상태로 인식하고 더 이상 삽입을 수행하지 않는다. (다음과 같은 상태)

[0] [1] [2] [3]
    front                 rear                

 - 해결 방법 1 : 저장된 원소들을 삭제 연산 이후 앞으로 당긴다. (but, 순차 자료에서 이동 작업은 연산이 복잡하여 효율성이 낮음)

 - 해결 방법 2 : 1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어있다 가정 => 원형 큐

원형 큐의 논리적 구조 (출처: IT COOKBOOK)


원형 큐

 - 1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어있다 가정한다

 - 초기 공백 상태 : front == rear == 0

 - front와 rear의 위치가 배열의 마지막 인덱스(n-1)에서 논리적인 다음 자리인 인덱스 0번으로 이동하기 위해 나머지 연산자(mod) 사용

 - 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front자리는 사용하지 않고 항상 빈자리로 유지한다

 

원형 큐의 연산

 - 삽입 : enQueue

EX )
(① 공백 큐 생성) : 큐가 생성되지 않은 최초 상태에서만 실행
② 원소 A삽입
③ 원소 B삽입

(① 공백 큐 생성)

   
[1] [2]
[0] [3]
front == rear == 0   

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

 rear == 1  
[1]               A              [2]
[0] [3]
front == 0  

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

   rear == 1
[1]              A                           B               [2]
[0] [3]
front == 0  

 - 삭제 : deQueue

EX )
① 원소 삭제

① 원소 삭제 : deQueue(cQ);

front == 0  rear == 1
[1]              A              B               [2]
[0] [3]
   

연결 큐

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

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

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

    ㄴ 변수 front : 첫 번째 노드를 가리키는 포인터 변수

    ㄴ 변수 rear : 마지막 노드를 가리키는 포인터 변수

 - 상태 표현

    ㄴ 초기 상태와 공백 상태 : front == rear == null

 - 연결 큐의 구조

100번지   200번지   300번지
A
200
B
300
C null
   

100

400
 front     rear   

 

연결 큐의 연산

 - 삽입

① 연결 큐를 생성한다. (최초 1회)
② (연결 큐가 생성되어 있을 시) 연결 큐가 공백인지 확인한다.
    -1 공백인 경우, 삽입할 새 노드에 front 포인터와 rear포인터를 가리킨다.
    -2 공백이 아닌 경우, 현재 큐의 마지막 노드 뒤에 새 노드를 삽입하고 rear 포인터가 가리키도록 한다.

① 연결 큐를 생성한다. (최초 1회)

new   100번지   front rear

100
item null null null

 (연결 큐가 생성되어 있을 시) 연결 큐가 공백인지 확인한다.

    -1 공백인 경우, 삽입할 새 노드에 front 포인터와 rear포인터를 가리킨다.

100번지
A null
 

100

100
 front   rear 

    -2 공백이 아닌 경우, 현재 큐의 마지막 노드 뒤에 새 노드를 삽입하고 rear 포인터가 가리키도록 한다.

100번지   200번지
A
200
B null
   

100

200
 front   rear 

 - 삭제

① front 포인터가 front 노드가 가리키던 노드를 가리키게 한다.
② 이번 연산이 끝나고 큐가 공백이 되는 경우, front 포인터와 rear 포인터를 null로 재설정한다.

① front 포인터가 front 노드가 가리키던 노드를 가리키게 한다.

100번지   200번지
A
200
B null
   

200

200
front   rear 

② 이번 연산이 끝나고 큐가 공백이 되는 경우, front 포인터와 rear 포인터를 null로 재설정한다.

front    rear 
 null
null


운영체제의 작업 큐

 - 프린터 버퍼 큐

    ㄴ CPU에서 프린터로 보낸 데이터 순서대로(선입선출, FIFO) 프린터에서 출력하기 위해 큐 사용

 - 스케줄링 큐

    ㄴ CPU 사용을 요청한 프로세서들의 순서를 스케줄링하기 위해 큐 사용

728x90
반응형