큐의 구현과 응용; 덱(deque)

큐

-> 먼저 들어온 항목이 먼저 나가는 특수한 선형 리스트, 선입선출(FIFO) 구조.

 

 

 

○ 큐 ADT

enqueue(q, item) :: = 새로운 원소 item을 큐 q에 삽입

dequeue(q) :: = 큐가 비어있지 않으면 큐 q에서 원소 삭제 후 반환

peek(q) :: = 큐가 비어있지 않으면 큐 q에서 원소 삭제하지 않고 원소 값만 반환

is_empty(q) :: = 큐가 비어있으면 true, 아니면 false를 반환

is_full(q) :: = 큐가 가득 차 있으면 true, 아니면 false를 반환

size(q) :: = 큐에 있는 원소의 개수를 반환 (length(q))

visit(q) :: = 큐에 있는 모든 원소 출력 (display(q), print(q))

 

 

 

○ 배열을 이용한 큐

 

· 선형 큐

: 배열을 선형으로 사용해 큐 구현. 삽입, 제거 연산을 위해서는 원소들을 이동시켜야 함. 비효율적이어서 잘 사용되지 않음. 가장 최근에 제거된 원소의 인덱스, 다음에 제거될 원소 하나 전 인덱스인 front와 가장 최근에 삽입된 원소의 인덱스 rear를 사용.

 

· 환형 큐

: 배열을 환형으로 사용해 큐 구현. front, rear뿐 아니라 원소 나타내는 변수 count를 따로 두기도 함.

front == rear면 공백상태, front==(rear+1) % MAX_QUEUE_SIZE면 포화상태. count가 존재하는 경우에는 count==0이면 공백상태, count==MAX_QUEUE_SIZE면 포화상태.

 

#환형 큐의 연산

#공백상태검출
int is_empty(QueueType *q){
    return (q->front == q->rear);
}

#포화상태검출
int is_full(QueueType *q){
    return (q-<front == (q->rear+1)%MAX_QUEUE_SIZE;
}

#삽입 연산
void enqueue(QueueType *q, element item){
    if(is_full(q))
    	error("큐가 포화상태입니다");
    else{
        q->rear = (q->rear+1) % MAX_QUEUE_SIZE;
        q->queue[q->rear] = item;
    }
}

#삭제 함수
element dequeue(QueueType *q){
    if(is_empty(q))
        error("큐가 공백상태입니다");
    else{
        q->front = (q->front+1) % MAX_QUEUE_SIZE;
        return q->queue(q->front);
    }
}

 

 

○ 연결리스트를 이용한 큐

·front는 삭제, rear는 삽입을 위해 유지하는 포인터이며, front는 연결리스트 맨 앞에 있는 노드를 가리키고 rear는 맨 뒤 노드 가리킴. 큐에 원소가 없는 경우에는 front가 NULL거나 둘다 동시에 NULL. 환형 연결리스트인 경우에는 rear만 존재해도 가능.

 

//삽입함수
void enqueue(QueueType *q, element item){
    QueuNode *temp = (QueueNode*)malloc(sizeof(QueueNode));
    if(temp = NULL)
        error("메모리 할당 에러");
    else{
        temp->item = item;
        temp->link = NULL;
        if(is_empty(q)){
            q->front = temp;
            q->rear = temp;
        }
        else{
            q->rear->link = temp;
            q->rear = temp;
        }
     }
}

//삭제함수
element dequeue(QueueType *q){
    QueuNode *temp = q->front;
    element item;
    
    if(is_empty(q))
        error("큐가 공백");
    else{
        item = temp->item;
        q->front = q->front->link;
        if(q->front == NULL)
            q->rear = NULL;
        free(temp);
        return item;
    }
}

 

 

○ 큐의 응용 ; 덱(deque, double-ended queue)

 

· 정의

: 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 특별한 큐

 

 

 

· 덱 ADT

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) :: = 덱의 뒤에 있는 원소를 삭제하지 않고 값 반환

 

 

· 덱의 구현

: 양쪽에서 삽입, 삭제 가능해야 하므로 일반적으로 이중연결리스트 사용.

 

typedef int element;

typedef struct DlistNode{
    element data;
    struct DlistNode *llink;
    struct DlistNode *rlink;
} DlistNode;

typedef struct DequeType{
    DlistNode *head;
    DlistNode *tail;
    int count;
} DequeType;

 

 

· 덱의 연산

//후단 삽입 연산
void add_rear(DequeType *dq, element item)
{
    DlistNode *new_node = create_node(dq->tail, item, NULL);
    if(is_empty(dq))
        dq->head = new_node;
    else
        dq->tail->rlink = new_node;
    dq->tail = new_node;
}

//전단 삽입 연산
void add_front(DequeType *dq, element item)
{
    DlistNode *new_node = create_node(NULL, item, dq->head);
    if(is_empty(dq))
        dq->tail = new_node;
    else
        dq->head->llink = new_node;
    dq->head = new_node;
}

//전단 삭제 연산
element delete_front(DequeType *dq)
{
    element item;
    DlistNode *removed_node;
    if(is_empty(dq)) error("공백 덱에서 삭제");
    else{
        removed_node = dq->head;
        item = removed_node->data;
        dq->head = dq->head->rlink;
        free(removed_node);
        if(dq->head == NULL)
            dq->tail = NULL;
        else
            dq->head->llink = NULL;
    }
    return item;
}

//후단 삭제 연산
element delete_rear(DequeType *dq)
{
    element item;
    DlistNode *removed_node;
    if(is_empty(dq)) error("공백 덱에서 삭제");
    else{
        removed_node = dq->tail;
        item = removed_node->data;
        dq->tail = dq->tail->llink;
        free(removed_node);
        if(dq->tail == NULL)
            dq->head = NULL;
        else
            dq->tail->rlink = NULL;
    }
    return item;
}