이중 연결 리스트 기반 데크(Dequeue) 개념

[ 이 게시물은 개념 설명 게시물이고 소스코드는 다음 게시물에 있습니다. ]

Dequeue는 디큐라고 발음하면 Queue의 Pop과 같은 발음이 나기에 '데크', '덱', '덱큐' 등등으로 부른다.

여기서는 덱이라고 칭하겠다.

우선 덱의 기능을 살펴보자면 

// 초기화 과정
void init(DequeType *dq)
{
    dq->head = dq->tail = NULL; // 처음 덱의 head와 tail은 NULL을 가리키도록
}
 

init 에 의해 처음 head와 tail은 NULL을 가리키게 된다.

그다음 

 
// 노드 생성
DlistNode *create_node(DlistNode *tail, Data val, DlistNode *head)
{
    DlistNode *new_node = (DlistNode *)malloc(sizeof(DlistNode)); // 메모리 할당 후
 
    if (new_node == NULL)
    {
        cout << "Memory allocation error!";
        exit(0);
    }
 
    new_node->frontLink = tail; // Newnode의 front링크부분이 front가 가리키는 노드를 가리키게 한다.
    new_node->data = val; // 데이터 입력
    new_node->rearLink = head; //  Newnode의 rear링크부분이 rear이 가리키는 노드를 가리키게 한다.
    return new_node;
}
 
 
// Deque 비었는지 확인
int DeqIsEmpty(DequeType *dq)
{
    if (dq->head == NULL) return TRUE;
    else return FALSE;
}
 
 
// 덱의 처음에 삽입
void pushFront(DequeType *dq, Data val)
{
    DlistNode *new_node = create_node(NULL, val, dq->head); // pushFront는 왼쪽에서 생기는 것이니 front는 NULL을 rear은 다음 것을 가리키게 해야한다.
 
    if (DeqIsEmpty(dq))
        dq->tail = new_node; // 첫 덱 생성 시
    else
        dq->head->frontLink = new_node;
    
    dq-head = new_node; // head를 Newnode를 보도록 한다.
}

하나의 노드를 pushFront 또는 pushRear으로 push하게 되면 다음과 같은 모습을 얻을 수 있다.

< 첫번째 PUSH 과정 > ( pushFront을 한다고 가정 )

코드를 분석 해 보자면, pushFront에서 create_node(NULL, val, dq->head);를 하게되는데

new_node의 frontlink가 첫번째 인자인 tail이 가리키는 값을 가리키도록 되어있다.

하지만 tail부분은 NULL인자이므로 frontlink는 NULL을 가리키게 된다.

다음 데이터 값을 입력시키고

세번째 인자인 dq->head로 구성된 head는 new_node->rink에 영향을 주고 현재 init다음 처음 push 된것이니 HEAD와 TAIL은 서로 NULL을 가리키고 있었다.

즉, new_node->rink = head; 또한 HEAD가 NULL을 가리키고 있었으니 NULL을 가리키게 된다.

그다음 if문에서 첫 덱의 생성이니 dq->tail = newnode;를 하게 되어 tail이 newnode를 가리키게 된다.

그다음 head도 newnode를 가리키게 된다. 

이후로 생기는 과정은 다음과 같다.

< 두번째 PUSH 과정 > ( pushRear을 한다고 가정 )

앞에서 만들어진 노드가 있고 새로 pushRear을 하게 된다면, 아래의 코드에 의해 코드 아래의 그림처럼 진행이 된다.

// 노드 생성
DlistNode *create_node(DlistNode *tail, Data val, DlistNode *head)
{
    DlistNode *new_node = (DlistNode *)malloc(sizeof(DlistNode)); // 메모리 할당 후
 
    if (new_node == NULL)
    {
        cout << "Memory allocation error!";
        exit(0);
    }
    new_node->frontLink = tail; // Newnode의 front링크부분이 tail이 가리키는 노드를 가리키게 한다.
    new_node->data = val; // 데이터 입력
    new_node->rearLink = head; //  Newnode의 rear링크부분이 head가 가리키는 노드를 가리키게 한다.
    return new_node;
}
 
// 덱의 마지막에 삽입
void pushRear(DequeType *dq, Data val)
{
    DlistNode *new_node = create_node(dq->tail, val, NULL); // Newnode를 생성한다
 
 
    if (DeqIsEmpty(dq))
        dq->head = new_node;
    else
        dq->tail->rearLink = new_node;
 
    dq->tail = new_node;
}
 

(front or rear)Push를 계속 하게 되면 아래와 같이 형성되고

Pop은 한번 이러한 방식으로 생각 해 보는것을 추천한다.