Deque

문제

Deque (Double-ended que) 이란?

 

 Deque는 "Double-ended que"의 약자로, Stack과 Queue를 일반화한 형태라고 볼 수 있으며, 앞 뒤로 통로가 있어 Push, Pop 명렬어을 통해 양방향으로 데이터를 넣고, 뺄 수 있는 형태의 자료 구조이다.

 

문제는 Backjoon 에서 10866번 문제이며, Deque 자료 구조에 대한 이해와 포인터, 구조체를 활용 연습을 위해 해당 문제를 풀게 되었다. 

• 출처 : 10866번: 덱 (acmicpc.net  

 

code)

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

// Structure
typedef struct NODE {
    struct NODE* p_prev;
    struct NODE* p_next;
    int data;
} NODE;

// Global variable
static int size = 0;

// Function prototypes.
void push(NODE** p_header, NODE** p_tailer, int data, int dir);
int pop(NODE** p_header, NODE** p_tailer, int dir);
int front(NODE* p_header);
int back(NODE* p_tailer);
int getSize();

// Main method
int main() {
    NODE* p_header = NULL, * p_tailer = NULL;
    unsigned short NofCommand = 0;
    char command[11];

    scanf("%hu", &NofCommand);

    int data = 0;
    for (unsigned short i = 0; i < NofCommand; i++) {
        scanf("%s", command);

        if (!strcmp(command, "push_front")) {
            scanf("%d", &data);
            push(&p_header, &p_tailer, data, 0);
            size++;
        }
        else if (!strcmp(command, "push_back")) {
            scanf("%d", &data);
            push(&p_header, &p_tailer, data, 1);
            size++;
        }
        else if (!strcmp(command, "pop_front")) {
            int pop_data = -1;
            if (size > 0) {
                pop_data = pop(&p_header, &p_tailer, 0);
                size--;
            }
            printf("%d\n", pop_data);
        }
        else if (!strcmp(command, "pop_back")) {
            int pop_data = -1;
            if (size > 0) {
                pop_data = pop(&p_header, &p_tailer, 1);
                size--;
            }
            printf("%d\n", pop_data);
        }
        else if (!strcmp(command, "size"))
            printf("%d\n", getSize());
        else if (!strcmp(command, "empty"))
            printf("%d\n", (getSize() > 0) ? 0 : 1);
        else if (!strcmp(command, "front"))
            printf("%d\n", front(p_header));
        else if (!strcmp(command, "back"))
            printf("%d\n", back(p_tailer));
        else
            puts("You entered wrong command.");
    }
    return 0;
}

// Extra methods.
void push(NODE** p_header, NODE** p_tailer, int data, int dir) {
    NODE* newNode = (NODE*)malloc(sizeof(NODE));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    newNode->data = data;
    newNode->p_next = NULL;
    newNode->p_prev = NULL;

    if (*p_header == NULL) {
        *p_header = newNode;
        *p_tailer = newNode;
        return;
    }

    if (!dir) {
        (*p_header)->p_prev = newNode;
        newNode->p_next = *p_header;
        *p_header = newNode;
    }
    else {
        (*p_tailer)->p_next = newNode;
        newNode->p_prev = *p_tailer;
        *p_tailer = newNode;
    }
}

int pop(NODE** p_header, NODE** p_tailer, int dir) {
    int temp_data = 0;
    NODE* temp_node = NULL;

    if (!dir) {
        temp_node = *p_header;
        temp_data = temp_node->data;
        *p_header = temp_node->p_next;

        if (*p_header != NULL)
            (*p_header)->p_prev = NULL;
        else
            *p_tailer = NULL;
    }
    else {
        temp_node = *p_tailer;
        temp_data = temp_node->data;
        *p_tailer = temp_node->p_prev;

        if (*p_tailer != NULL)
            (*p_tailer)->p_next = NULL;
        else
            *p_header = NULL;
    }

    free(temp_node);
    return temp_data;
}

int front(NODE* p_header) {
    if (p_header == NULL) return -1;
    else return p_header->data;
}

int back(NODE* p_tailer) {
    if (p_tailer == NULL) return -1;
    else return p_tailer->data;
}

int getSize() {
    return size;
}

 

• Deque를 구성하는 노드는 구조체를 통해 구현하였으며, 구조체의 맴버는 다음과 같다.

       1) 정수 데이터 (data)

       2) 이전 노드의 메모리 주소값을 저장하는 포인트 변수 ( p_prev )

       3) 다음 노드의 메모리 주소값을 저장하는 포인트 변수 ( p_next )

• Deque의 첫 번째 노드의 주소 값을 저장하기 위해 포인트 변수, p_header를 정의하였으며,
  Deque의 마지막 노트의 주소 값을 저장하기 위해 포인트 변수, p_tailer 를 정의하였다.
• Deque의 명령어를 처리하기 위해 다음과 같은 함수들을 정의하였다.
  - push 함수 : p_header와 p_tailer, data, dir을 매개 변수로 받아 세 가지 경우의 수로 나누어 처리한다.
     ▶ Deque가 완전히 비어 있는 경우 (p_header == NULL인 경우)    
     ▶ dir = 0 인 경우 ( Front로 push하는 경우 )
     ▶ dir = 1 인 경우 ( Back로 push하는 경우 )
     ▶중요) 만약 새로운 노드를 지역 변수로 생성할 경우 push 함수가 Return 되었을 때, 새로운 노드가
        저장된 메모리 공간이 Return과 함께 사라진다는 문제가 발생한다.
        이러한 함수가 Return되어도 데이터가 사라지는 것을 방지하기 위해 동적 메모리 할당을 사용하여
        새로운 노드가 저장된 메모리 공간이 Return과 함께 사라지는 것이 아닌 사용자가 원하는 시점에
         free함수를 통해 해체함으로서 해결할 수 있다.
  
  - pop 함수 : p_header와 p_tailer, dir을 매개 변수로 받아 pop하고자 하는 노드의 데이터를 꺼낸 뒤, 
                     동적 할당 받은 노드를 free함수를 통해 해체한다.
     ▶주의) 동적 할당 받은 노드는 받드시 해당 노드의 주소값을 통해 해체가 가능하기 때문에 
                  해당 노드의 값을 임시저장할 뿐만 아니라 해당 노드의 주소값 또한 임시저장해야 할 필요
                  가 있다.