자료구조 :: 큐(3) double-ended-queue

# Deque

deque.cpp

deque는 double-ended-queue의 줄임말로써 큐의 전단과 후단에서 모두 삽입 삭제가 가능한 큐를 의미한다.
deque는 스택과 큐의 연산들을 모두 가지고 있다.
 
전단(front) 데이터 삽입,삭제,획득 및  후단(rear) 데이터 삽입,삭제,획득이 가능하다.

#include <stdio.h> 
#include <stdlib.h> 

#defineTRUE1
#defineFALSE0
typedefint element;        // 요소의 타입

typedefstruct DlistNode {    // 노드의 타입
    element data; 
struct DlistNode *llink; 
struct DlistNode *rlink; 
} DlistNode; 

typedefstruct DequeType {    // 덱의 타입
    DlistNode *head; 
    DlistNode *tail; 
} DequeType; 
//
void error(char *message) 
{ 
    fprintf(stderr,"%s\n",message); 
    exit(1); 
} 
//
void init(DequeType *dq) 
{ 
    dq->head=dq->tail=NULL; 
} 

// 
DlistNode *create_node(DlistNode *llink, element item,  
                DlistNode *rlink) 
{ 
  DlistNode *new_node = (DlistNode *)  
            malloc(sizeof(DlistNode)); 
if(new_node == NULL) 
        error("메모리 할당 오류"); 
  new_node->llink = llink; 
  new_node->data = item; 
  new_node->rlink = rlink; 
return new_node; 
} 
//
int is_empty(DequeType *dq) 
{ 
if( dq->head == NULL ) returnTRUE; 
elsereturnFALSE; 
} 
// 덱의 마지막에 삽입
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; 
}  
//
void display(DequeType *dq) 
{ 
    DlistNode *p; 
    printf("( "); 
for(p=dq->head;p!=NULL;p=p->rlink){ 
        printf("%d ",p->data); 
    } 
    printf(")\n"); 
} 

//
int main() 
{ 
    DequeType deque; 

    init(&deque); 
    add_front(&deque, 10); // 10
    add_front(&deque, 20); // 20 10
    add_rear(&deque, 30);  // 20 10 30
    add_rear(&deque, 40);  // 20 10 30 40
    display(&deque); 

    delete_front(&deque); // 10 30 40
    delete_rear(&deque);  // 10 30 
    display(&deque); 
}