[자료구조] 큐 / 덱

큐

• 컴퓨터의 기본 자료구조 중 하나로 먼저 들어온 데이터가 먼저 나가는 구조로 되어 있습니다. 즉, FIFO(First-In First-Out) 선입선출.
• 한쪽에서는 데이터가 추가되고 한쪽에서는 데이터가 삭제되는 구조를 가지고 있음

 

큐 ADT

객체: 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)) queue_full 오류;
    	else q의 끝에 e를 추가한다.
    dequeue(q) ::=
    	if(is_empty(q)) queue_empty 오류;
        else q의 맨 앞에 있는 e를 제거하여 반환한다.
	peek(q) ::=
    	if(is_empty(q)) queue_empty 오류;
        else q의 맨 앞에 있는 e를 읽어서 반환한다.

 

 

 

선형큐

• 정수형 1차원 배열을 정의
• 삽입, 삭제를 다루기 위한 변수 front, rear
• front는 큐의 첫번째 요소, rear은 큐의 마지막 요소

 

 

 

원형큐

• 선형큐 개념에서 끝에 도달하면 마지막과 연결해주는 개념
• front는 항상 큐의 첫 번쨰 요소의 하나 앞, rear는 마지막 요소

 

원형큐에서의 삽입 알고리즘

enqueue(Q, x):
	rear <- (rear + 1) % MAX_QUEUE_SIZE;
    Q[rear] <- x;

 

원형큐에서의 삭제 알고리즘

dequeue(Q):
	front <- (front + 1) % MAX_QUEUE_SIZE;
    return Q[front]

 

 

 

 

덱

덱(deque)은 double-ended queue의 줄임말로서 큐의 front와 rear에서 모두 삽입과 삭제가 가능한 큐를 의미한다.

 

 

 

덱 ADT

객체: 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(q) ::= 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환한다.
    get_rear(q) ::= 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환한다.