[자료구조] 큐(Queue), 덱(Deque)

 

 

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

 

 

큐(Queue)

• 선입선출(FIFO: First-In First-Out) 입출력 형태를 갖는다.
• 삽입과 삭제가 일어나는 위치가 다르다.
  = 삽입과 삭제가 큐의 양 끝에서 일어난다.
   rear(후단)  : 큐에서 삽입이 일어나는 곳
   front(선단)  : 큐에서 삭제가 일어나는 곳

 

 

큐의 연산

객체 : 0개 이상의 요소들로 구성된 선형 리스트
연산 :
    create(max_size) ::= 최대 크기가 max_size인 공백 큐를 생성
    init(q) ::= 큐 초기화
    is_empty(q) ::=
    	if(size == 0) return TRUE;
        else return FALSE:
    is_full(q) ::=
    	if(size == max_size) return TRUE;
        else return FALSE;
    enqueue(q, e) ::=
    	if(is_full(q)) ERROR_QUEUE_FULL;
        else q의 끝에 e를 추가
    dequeue(q) ::=
    	if(is_empty(q)) ERROR_QUEUE_EMPTY;
        else q의 맨 앞에 있는 e를 제거하여 반환
    peek(q) ::=
    	if(is_empty(q)) ERROR_QUEUE_EMPTY;
        else q의 맨 앞에 있는 e를 읽어서 반환

enqueue(Q, x) ::=
    rear<-(rear + 1) % MAX_QUEUE_SIZE;    // 배열 크기를 넘어가지 않게 하기 위해 큐 사이즈로 나눠줌
    Q[rear]<-x;
dequeue(Q) ::=
    front<-(front + 1) % MAX_QUEUE_SIZE;
    return Q[front];

원형 큐일 경우 삽입과 삭제 알고리즘이 달라진다.

• enqueue : 삽입 연산. 큐의 맨 뒤에 새로운 요소를 추가
• dequeue : 삭제 연산. 큐의 맨 앞에 있는 요소가 삭제되면서 반환
• peek : 맨 앞에 있는 요소를 읽어서 반환 (삭제가 일어나지 X)
• is_empty : 큐가 공백 상태인지 검사
• is_full : 큐가 포화 상태인지 검사
• create : 큐 생성
• init : 큐 초기화

 

 

큐의 종류

• 선형 큐(linear queue)
  - front와 rear이 증가만 하기 때문에 경우에 따라 배열의 앞부분을 사용할 수 없음
  - 주기적으로 모든 요소를 앞쪽으로 이동시켜야 하기 때문에 비효율적
• 원형 큐(circular queue)
  선형 큐의 단점을 보완하기 위해 처음과 끝을 연결한 개념.
  공백 상태 : ``front == rear``
  포화 상태 : front가 rear보다 한 칸 앞에 있는 경우
  
  - 공백상태와 포화상태를 구분하기 위한 방법
      1. 항상 큐의 한자리 이상을 비우기
      2. 원소의 개수를 저장하는 변수를 지정

 

 

큐의 응용

• 버퍼
• 인쇄 작업 큐
• 운영체제의 작업 스케줄링

 

대기 행렬 이론, 큐잉 이론(queueing theory)

 : 대기 행렬을 수학적으로 다루는 이론. 경영관리, 산업공학, 통신 네트워크의 성능 분석 및 설계(패킷 스케줄링 정책, 자원관리)등 여러 분야에서 사용한다.

 

 

 

 

 

---

덱(Deque, double-ended queue)

  큐의 전단(front) 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다.

 

 

덱의 연산

객체 : n개의 element형의 요소들의 순서 있는 모임
연산 :
    create() ::= 덱 생성
    init(dq) ::= 덱 초기화
    is_empty(dq) ::= 덱이 공백상태인지 검사
    is_full(dq) ::= 덱이 포화상태인지 검사
    add_front(dq, e) ::= 덱의 앞에 요소 추가
    add_rear(dq, e) ::= 덱의 뒤에 요소 추가
    delete_front(dq) ::= 덱의 앞에 있는 요소를 반환한 다음 삭제
    delete_rear(dq) ::= 덱의 뒤에 있는 요소를 반환한 다음 삭제
    get_front(dq) ::= 덱의 앞에 있는 요소를 삭제하지 않고 반환
    get_rear(dq) ::= 덱의 뒤에 있는 요소를 삭제하지 않고 반환

• add_front : 덱의 앞에 요소를 추가
• add_rear : 덱의 뒤에 요소를 추가
• delete_front : 덱의 앞에 있는 요소가 삭제되면서 반환
• delete_rear : 덱의 뒤에 있는 요소를 삭제되면서 반환
• get_front : 덱의 앞에 있는 요소를 반환 (삭제되지 X)
• get_rear : 덱의 뒤에 있는 요소를 반환 (삭제되지 X)
• is_empty : 덱이 공백 상태인지 검사
• is_full : 덱이 포화 상태인지 검사
• create : 덱 생성
• init : 덱 초기화

 

 

덱의 연산 비교

  덱은 스택과 큐의 연산들을 모두 가지고 있다.

	스택(stack)	큐(queue)	덱(deque)
앞에서 삽입			add_front
앞에서 삭제		dequeue	delete_front
뒤에서 삽입	push	enqueue	add_rear
뒤에서 삭제	pop		delete_rear