큐

스택과 큐는 추상적 자료구조이다.

언제 큐와 스택을 쓰는가?

브라우저에서 뒤로가기 누르면 스택을쓰는것!

뭔가를쓰다가 뒤로가기 하면 스택이닷!

되돌리기 = 스택에 차곡차곡쌓다가 스택으로 가서 과거 되돌리기

이메일 전달, 푸쉬알림, 쇼핑물 주문처리, 콜센터의 백엔드 : 큐

 

 

ƒ 스택과 비슷한 삽입과 삭제의 위치가 제한되어있는 유한 순서 리스트

ƒ 큐는 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조

• 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입(First-In)한 원소는 맨 앞에 있다가 가장 먼저 삭제(First-Out)됨

☞ 선입선출 구조 (FIFO, First-In-First-Out)

 

삽입: enQueue

삭제 : deQueue

 

rear : 저장된 원소 중 마지막 원소

front : 제일 앞에있는것. 빠지기 전까지 변하지 않음

 

 

순차 큐

ƒ 1차원 배열을 이용한 큐

• 큐의 크기 = 배열의 크기

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

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

 

ƒ 상태 표현

• 초기 상태 : front = rear = -1

• 공백 상태 : front = rear

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

 

ƒ 초기 공백 큐 생성 알고리즘

• 크기가 n인 1차원 배열 생성

• front와 rear를 -1로 초기화

CreateQueue(){
	Q[n];
    front <- -1;
    rear <- -1;
}

 

 

ƒ 공백 큐 검사 알고리즘과 포화상태 검사 알고리즘

• 공백 상태 : front = rear

isEmpty(Q){
	if(front == rear) then return true;
    else return false;
}

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

isFull(Q){
	if (rear = n- 1) then return true;
    else return false;
}

ƒ 큐의 삽입 알고리즘

enQueue(Q,item){
	if(isFull(Q)) then Queue_Full();
    else{
    	rear <- rear +1;
        Q[rear] <- item;
        }
}

마지막 원소의 뒤에 삽입해야 하므로

① 마지막 원소의 인덱스를 저장한 rear의 값을 하나 증가시켜 삽입할 자리 준비

② 수정한 rear값에 해당하는 배열원소 Q[rear]에 item을 저장

 

ƒ 큐의 삭제 알고리즘

deQueue(Q){
	if (isEmpty(Q)) then Queue_Empty();
    else {
     	front <- front +1;
        return Q[front];
        }
   }

• 가장 앞에 있는 원소를 삭제해야 하므로

① front의 위치를 한자리 뒤로 이동하여 큐에 남아있는 첫 번째 원소의 위치로 이동하여 삭제할 자리 준비

② front 자리의 원소를 삭제하여 반환

원래 프론트는 -1 이었으니까 이동을 해줘야 삭제할 원소를 찾을 수 있다.

 

ƒ 큐의 검색 알고리즘

peek(Q)
{
	if (isEmpty(Q)) then Queue_Empty();
    else return Q[front + 1];
    }

가장 앞에 있는 원소를 검색하여 반환하는 연산

① 현재 front의 한자리 뒤(front+1)에 있는 원소, 즉 큐에 있는 첫 번째 원소를 반환

 

순차 큐의 잘못된 포화상태 인식

• 큐에서 삽입과 삭제를 반복하면서 앞부분에 빈자리가 있지만 rear=n-1 상태이므로 포화상태로 인식하고 더 이상의 삽입을 수행하지 않는다.

 

ƒ 순차 큐의 잘못된 포화상태 인식의 해결 방법-1

• 저장된 원소들을 배열의 앞부분으로 이동시키기

− 순차자료에서의 이동 작업은 연산이 복잡하여 효율성이 떨어짐

 

ƒ 순차 큐의 잘못된 포화상태 인식의 해결 방법-2

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

⇒ 원형 큐

 

ƒ 원형 큐의 구조

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

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

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

사용조건) 공백 상태와 포화 상태 구분을 쉽게 하기 위해서 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠

 

 

ƒ 초기 공백 원형 큐 생성 알고리즘 • 크기가 n인 1차원 배열 생성 • front와 rear를 0 으로 초기화

createQueue(){
	cQ[n];
    front < - 0;
    rear <- 0;
    }

ƒ 원형 큐의 공백상태 검사 알고리즘과 포화상태 검사 알고리즘

isEmpty(Q){
	if(front == rear) then return true;
    else return false;
    }
    
isFull(cQ){
	if(((rear+1)mod n) == front ) then return true;
    else return false;
    }

 

원형 큐의 삽입 알고리즘

① rear의 값을 조정하여 삽입할 자리를 준비 : rear ← (rear+1) mod n;

② 준비한 자리 cQ[rear]에 원소 item을 삽입

 

 

 

ƒ 원형 큐의 삭제 알고리즘

① front의 값을 조정하여 삭제할 자리를 준비

② 준비한 자리에 있는 원소 cQ[front]를 삭제하여 반환

 

ƒ 크기가 4인 원형 큐에서 큐를 생성하고 삽입·삭제하는 연산 과정

 

① 공백 원형 큐 생성 : createQueue();

front < -0

rear <- 0

 

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

rear < - (0+1) mod 4;

cQ[1] <- A;

 

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

rear <- (1+1) mod 4;

cQ[2] <- B;

 

④ 원소 삭제 : deQueue(cQ); (삭제 데이터 : A)

front <- (0+1) mod 4;

return cQ[1]

 

 

---

연결 큐

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

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

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

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

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

 

ƒ 공백 연결 큐 생성 알고리즘

• 초기화 : front = rear = null

createLinkedQueue(){
	front <- NULL;
    rear <- NULL;
    }

ƒ 연결 큐의 공백 상태 검사 알고리즘

• 공백 상태 : front = null

enQueue(LQ, item){
	new<- getNode();
    new.data <- item;
    new.link <-NULL;
    if( front = NULL)then{
    	rear <- new;
        front <- new;
        }
    else{
    	rear.link <- new;
        rear <- new;
        }
    }

연결 큐의 원소 삭제 알고리즘

deQueue(LQ){
	if (isEmpty(LQ)) then Queue_Empty();
    else{
    	old <- front;
        item <- front.data;
        front <-front.link;
        if(isEmpty(LQ)) then rear <- NULL;
        returnNode(old);
        return item;
        }
   }

 

연결 큐의 원소 검색 알고리즘

• 연결 큐의 첫 번째 노드, 즉 front 노드의 데이터 필드 값을 반환

 

---

™ 데크(Deque : double-ended queue)

ƒ 큐 두 개 중 하나를 좌우로 뒤집어서 붙인 구조,

큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할 수 있도록 확장한 자료구조

앞 뒤 둘다 넣을 수 있도록

ƒ 데크의 구현

• 양쪽 끝에서 삽입/삭제 연산을 수행하면서 크기 변화와 저장된 원소의 순서 변화가 많으므로 순차 자료구조는 비효율적임

• 양방향으로 연산이 가능한 이중 연결 리스트를 사용

 

 

운영체제의 작업 큐

ƒ 프린터 버퍼 큐(Printer Buffer Queue)

• CPU에서 프린터로 보낸 데이터 순서대로(선입선출) 프린터에서 출력하기 위해서 선입선출 구조의 큐 사용

• CPU에서 데이터를 내보내는 출력 속도는 프린터의 출력 속도보다 훨씬 빠름

• CPU가 프린터의 출력이 끝날 때까지 기다렸다가 다음 데이터를 내보낸다면 기다리는 시간만큼 CPU도 다른 작업을 수행할 수 없어서 효율이 떨어짐

• 이런 문제를 보완하기 위해서 프린터 버퍼 큐를 사용

• CPU가 출력으로 내보내는 데이터를 프린터 버퍼 큐에 삽입하고 프린터가 버퍼 큐에 있는 작업을 순서대로 처리하면서 끝난 작업은 버퍼 큐에서 삭제

 

ƒ 스케줄링 큐(Scheduling Queue)

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

• CPU를 사용할 프로세스들을 준비 큐에 삽입하면 순서대로 준비 큐에서 꺼내서 CPU를 사용

• CPU를 사용하던 프로세스가 다른 처리를 기다리는 대기 상태가 되면 대기 큐에 삽입하여 대기 상태의 프로세스들을 순서대로 관리함