[자료구조] ep6-3) 데크(Deque)

ㅇ데크(Double-Ended Queue) ADT: 임의의 개체들을 저장하며, 스택과 큐의 합체 방식으로 작동한다

삽입(add)과 삭제(delete)는 앞(front)과 뒤(rear)라 불리는 양쪽 끝 위치에서 수행

쉽게 말해서, 양쪽 방향으로의 add/delete 가 둘 다 가능하다

 

 

 

역시 마찬가지로 데크는 배열과 리스트 2가지 방법으로 구현할 수 있다

 

1. 이중연결리스트에 기초한 데크

똑같이 삽입과 삭제가 특정 위치에서만 수행되므로, 특별노드는 불필요

 

2. 배열에 기초한 데크

똑같이 선형 배열은 비효율적이므로, 원형 배열을 사용한다

또 똑같이 빈 큐를 만원 큐로부터 차별하기 위해 '한 개의 빈 방'을 둔다

 

 

 

 

 

 

 

문제) 데크는 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 자료구조다. 헤더 노드와 트레일러 노드가 없는 이중연결리스트를 사용하여 아래에 정의된 데크 함수들을 구현하시오.

◦ 초기 상태
- 주의 : 명령 수행 도중 원소가 모두 삭제되어 데크가 비는 경우에도 아래 초기 상태가 되어야 함.

 

◦ 데크 연산
- add_front(deque, X) : deque의 앞에 원소 X를 추가(교안의 push와 동일).
- add_rear(deque, X) : deque의 뒤에 원소 X를 추가(교안의 inject와 동일).
- delete_front(deque) : deque의 앞에 있는 원소를 반환한 다음 삭제(교안의 pop과 동일).

- delete_rear(deque) : deque의 뒤에 있는 원소를 반환한 다음 삭제(교안의 eject와 동일).

- print(deque) : deque의 모든 원소들을 전단에서 후단 방향으로 차례로 출력.

 

◦ 입출력 형식:
1) 첫 번째 라인: 명령의 개수 n
2) 두 번째 이후 라인: n개의 명령이 한 줄에 하나씩 차례로 입력됨.

- 하나의 라인에는 명령의 종류, 삽입 명령인 경우 삽입할 원소(양의 정수).

- 명령의 종류: 다음과 같이 대문자로 된 명령이 주어짐.

AF(add_front), AR(add_rear), DF(delete_front), DR(delete_rear), P(print)

※ underflow 발생 시, 화면에 underflow를 출력하고 프로그램 종료.

 

test case

 

 

 

 

(전체코드)

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

typedef struct NODE {
    int e;
    struct NODE* next;
    struct NODE* prev;
} NODE;

void addFront(int e);
void addRear(int e);
int deleteFront();
int deleteRear();
void print();

NODE* g_front = NULL; // 리스트의 front 노드를 가리키는 전역 노드 포인터
NODE* g_rear = NULL; // 리스트의 rear 노드를 가리키는 전역 노드 포인터
int g_N = 0; // 리스트 전체 크기(노드의 총 개수)
int g_isError = 0;

int main() {
    int n; // 입력의 개수
    char cmd[3] = {0};
    int e;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf(" %s", cmd);
        if (strcmp(cmd, "AF") == 0) {
            scanf(" %d", &e);
            addFront(e);
        }
        else if (strcmp(cmd, "AR") == 0) {
            scanf(" %d", &e);
            addRear(e);
        }
        else if (strcmp(cmd, "DF") == 0) {
            deleteFront();
        }
        else if (strcmp(cmd, "DR") == 0) {
            deleteRear();
        }
        else if (strcmp(cmd, "P") == 0) {
            print();
        }

        if (g_isError == 1) {
            return 0;
        }
    }

    while (g_front != NULL) {
        NODE* temp = g_front;
        g_front = g_front->next;
        free(temp);
    }
    return 0;
}

void addFront(int e) {
    if (g_N == 0) {
        NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
        newNode->e = e;
        newNode->prev = NULL;
        newNode->next = NULL;
        g_front = newNode;
        g_rear = newNode;

        g_N++;
        return;
    }

    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
    newNode->e = e;
    newNode->prev = NULL;

    newNode->next = g_front;
    g_front->prev = newNode;
    g_front = newNode; // g_front가 newNode를 가리켜야 함

    g_N++;
}

void addRear(int e) {
    if (g_N == 0) {
        NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
        newNode->e = e;
        newNode->prev = NULL;
        newNode->next = NULL;
        g_front = newNode;
        g_rear = newNode;

        g_N++;
        return;
    }

    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
    newNode->e = e;
    newNode->next = NULL;

    g_rear->next = newNode;
    newNode->prev = g_rear;
    g_rear = newNode; // g_rear가 newNode를 가리켜야 함

    g_N++;
}

int deleteFront() {
    if (g_N == 0) {
        printf("underflow");
        g_isError = 1;
        return 0;
    }
    else if (g_N == 1) {
        int e = g_front->e;
        NODE* temp = g_front;
        free(temp);

        g_N--;
        g_front = NULL;
        return e;
    }
    else if (g_N > 1) {
        int e = g_front->e;
        NODE* temp = g_front;
        g_front = g_front->next;
        temp->next->prev = NULL;
        temp->next = NULL;
        free(temp);

        g_N--;
        return e;
    }
}

int deleteRear() {
    if (g_N == 0) {
        printf("underflow");
        g_isError = 1;
        return 0;
    }
    else if (g_N == 1) {
        int e = g_rear->e;
        NODE* temp = g_rear;
        free(temp);

        g_N--;
        g_rear = NULL;
        return e;
    }
    else if (g_N > 1) {
        int e = g_rear->e;
        NODE* temp = g_rear;
        g_rear = g_rear->prev;
        temp->prev->next = NULL;
        temp->prev = NULL;
        free(temp);

        g_N--;
        return e;
    }
}

void print() {
    NODE* temp = g_front;
    while (temp != NULL) {
        printf(" %d", temp->e);
        temp = temp->next;
    }
    printf("\n");
}

 

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님), C언어로 쉽게 풀어 쓴 자료구조(천인국)