이중 연결 리스트 기반 데크(Dequeue) 소스 코드

- main.cpp -

 
#include "DeqHeader.h"
 
int main()
{
    DequeType deque;
 
    init(&deque);
 
    int num;
    int value;
    while (1)
    {
        cout << "1. 왼쪽 push " << "\n" << "2. 왼쪽 pop" << "\n" << "3. 오른쪽 push" << "\n" << "4. 오른쪽 pop" << "\n" << "5. deQue 출력" << "\n" << "6. 종료\n " << endl;
 
        cout << "원하는 번호를 입력하세요. : ";
        cin >> num;
 
        switch (num)
        {
            case 1: // 왼쪽 push
            {
                cout << "값 입력 : ";
                cin >> value;
 
                pushFront(&deque, value);
                cout << endl;
                break;
            }
            case 2: // 왼쪽 pop
            {
                popFront(&deque); 
                break;
            }
            case 3: // 오른쪽 push
            {
                cout << "값 입력 : ";
                cin >> value;
        
                pushRear(&deque, value);
                cout << endl;
                break;
            }
            case 4: // 오른쪽 pop
            {
                popRear(&deque);
                break;
            }
            case 5:
            {
                display(&deque); // 덱 출력
                cout << endl;
                break;
            }
            case 6:
            {
                return 0;
            }
        }
 
    }
 
    return 0;
}

- DeqFunc.cpp -

#include "DeqHeader.h"
 
// 초기화 과정
void init(DequeType *dq)
{
    dq->head = dq->tail = NULL; // 처음 덱의 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링크부분이 tail이 가리키는 노드를 가리키게 한다.
    new_node->data = val; // 데이터 입력
    new_node->rearLink = head; //  Newnode의 rear링크부분이 head가 가리키는 노드를 가리키게 한다.
    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를 보도록 한다.
}
 
// 덱의 마지막에 삽입
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;
}
 
 
// 덱의 처음 데이터 삭제
Data popFront(DequeType *dq)
{
    Data val;
    DlistNode *removed_node;
 
    if (DeqIsEmpty(dq)) // 덱이 비었을 때
    {
        cout << "Error : Deq Is Empty!";
        exit(0);
    }
    else {
        removed_node = dq->head; // removed_node는 head가 가리키고 있던 것을 지정한다.
        val = removed_node->data; // pop되는 데이터의 값을 받는다.
        dq->head = dq->head->rearLink; // head를 rearLink가 가리키고 있던 곳으로 가리키게 한다. 즉, 한칸 오른쪽 것
        free(removed_node); // 메모리 해제
        if (dq->head == NULL)
            dq->tail = NULL;
        else
            dq->head->frontLink = NULL;
    }
    return val; // 데이터 반환
}
 
// 덱의 마지막 데이터 삭제
Data popRear(DequeType *dq)
{
    Data val;
    DlistNode *removed_node;
 
    if (DeqIsEmpty(dq)) // 덱이 비었을 때
    {
        cout << "Error : Deq Is Empty!";
        exit(0);
    }
    else {
        removed_node = dq->tail;
        val = removed_node->data;
        dq->tail = dq->tail->frontLink;
        free(removed_node);
 
        if (dq->tail == NULL)
            dq->head = NULL;
        else
            dq->tail->rearLink = NULL;
    }
    return val;
}
 
// 덱 출력
void display(DequeType *dq)
{
    DlistNode *p;
    printf("( ");
    for (p = dq->head; p != NULL; p = p->rearLink) // 처음부터 null 가리킬 때 까지
    {
        printf("%d ", p->data);
    }
    printf(")\n");
}
 

- DeqHearder.h -

#pragma once
#include <iostream>
#include <stdio.h> 
#include <stdlib.h> 
 
using namespace std;
 
#define TRUE 1
#define FALSE 0
typedef int Data;   // int를 Data로 선언   
 
// 노드의 타입
typedef struct DlistNode
{
    Data data;
    struct DlistNode *frontLink;
    struct DlistNode *rearLink;
} DlistNode;
 
// 덱의 타입
typedef struct DequeType
{
    DlistNode *head;
    DlistNode *tail;
} DequeType;
 
// 덱 초기화
void init(DequeType *dq);
 
// 노드 생성
DlistNode *create_node(DlistNode *tail, Data val, DlistNode *head);
 
// 덱이 비었는지 확인
int DeqIsEmpty(DequeType *dq);
 
// 앞으로 Push
void pushFront(DequeType *dq, Data val);
 
// 뒤로 Push
void pushRear(DequeType *dq, Data val);
 
// 앞으로 Pop
Data popFront(DequeType *dq);
 
// 뒤로 Pop
Data popRear(DequeType *dq);
 
// 큐 상황 출력
void display(DequeType *dq);