자료구조

덱(Deque)

비선형구조 2017. 5. 31. 11:47


덱(Deque)

데이터를 앞으로도 뒤로도 넣을 수 있고,

앞으로도 뒤로도 뺄 수 있는 자료구조이다.


양반향 연결 리스트 기반으로 '덱' 구현.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <stdio.h>
 
#define FIRST        0
#define LAST         1
 
typedef struct Node
{
    int Data;
    struct Node* pNext;
    struct Node* pUnder;
}NODE;
 
typedef struct DeQue
{
    int Count;
    NODE* pHead;
    NODE* pTail;
}DQ;
 
void InitDQ(DQ* _dq)
{
    _dq->Count = 0;
    _dq->pHead = NULL;
    _dq->pTail = NULL;
}
 
bool isEmpty(DQ* _dq)
{
    if(_dq->pHead == NULL)
        return false;
    return true;
}
 
void push(DQ* _dq, int Data, int start = LAST)
{
    NODE* NewNode = new NODE;
    NewNode->Data = Data;
    NewNode->pNext = NULL;
    NewNode->pUnder = NULL;
 
    if(_dq->pHead == NULL)
    {
        _dq->pHead = NewNode;
        _dq->pTail = NewNode;
    }
    else
    {
        if(start == FIRST)
        {
            NewNode->pNext = _dq->pHead;
            _dq->pHead->pUnder = NewNode;
            _dq->pHead = NewNode;
        }
        else
        {
            _dq->pTail->pNext = NewNode;
            NewNode->pUnder = _dq->pTail;
            _dq->pTail = NewNode;
        }
    }
}
 
int peek(DQ * _dq, int start = LAST)
{
    if(_dq->pHead == NULL || _dq->pTail == NULL)
        return -1;
 
    if(start == FIRST)
        return _dq->pHead->Data;
    return _dq->pTail->Data;
}
 
void pop(DQ * _dq, int start = LAST)
{
    if(_dq->pHead == NULL || _dq->pTail == NULL)
        return;
 
    NODE* pRemove;
    if(start == FIRST)
    {
        pRemove = _dq->pHead;
        _dq->pHead = _dq->pHead->pNext;
        _dq->pHead->pUnder = NULL;
    }
    else
    {
        pRemove = _dq->pTail;
        _dq->pTail = _dq->pTail->pUnder;
        _dq->pTail->pNext = NULL;
    }
    delete pRemove;
}
 
void DisPlay(DQ* _dq, int start = FIRST)
{
    if(_dq->pHead == NULL || _dq->pTail == NULL)
    {
        printf("출력할 데이터가 없슴돠 \n");
        return;
    }
 
    if(start == FIRST)
    {
        NODE* pNode = _dq->pHead;
        while(pNode != NULL)
        {
            printf("%d ", pNode->Data);
            pNode = pNode->pNext;
        }
    }
    else
    {
        NODE* pNode = _dq->pTail;
        while(pNode != NULL)
        {
            printf("%d ", pNode->Data);
            pNode = pNode->pUnder;
        }
    }
 
    printf("\n");
}
 
void main()
{
    DQ* dq = new DQ[sizeof(DQ)];
    InitDQ(dq);
 
    for(int i = 0; i < 5; i++)
        push(dq, i);
    DisPlay(dq);
}
cs


저작자표시 비영리 변경금지 (새창열림)