덱(Deque)

덱(Deque)

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

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

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

#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);
}