[자료구조] 덱 [C언어]

이번 시간에는 덱에 대해서 알아보자.

덱 Deque(Double-ended-queue)

덱(deque)은 double-ended queue의 줄임말로써 후단(rear)으로만 데이터를 삽입했던 기존 선형 큐, 원형 큐와 달리 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐다.

[코드구현]

// 덱

#include <stdio.h>
#include <malloc.h>

typedef char element;

typedef struct DQNode
{
	element data;
	struct DQNode* llink;
	struct DQNode* rlink;
}DQNode;

typedef struct
{
	DQNode* front, * rear;
}DQType;


DQType* createDQue()
{
	DQType* DQ;
	DQ = (DQType*)malloc(sizeof(DQType));
	DQ->front = NULL;
	DQ->rear = NULL;
	return DQ;
}


//addRaer 함수 구현하기.

void addRear(DQType* DQ, element item)
{
	DQNode* newnode = (DQNode*)malloc(sizeof(DQNode));
	newnode->data = item; //여기서 newnode ==> ㅁㅁ[item]ㅁ
	if (DQ->front == NULL)
	{
		DQ->front = newnode;
		DQ->rear = newnode;
		newnode->rlink = NULL;
		newnode->llink = NULL;
	}
	else
	{
		DQ->rear->rlink = newnode;
		newnode->rlink = NULL;
		newnode->llink = DQ->rear;
		DQ->rear = newnode;
	}

}

void addFront(DQType* DQ, element item)
{
	DQNode* newnode = (DQNode*)malloc(sizeof(DQNode));
	newnode->data = item;
	if (DQ->front == NULL)
	{
		DQ->front = newnode;
		DQ->rear = newnode;
		newnode->rlink = NULL;
		newnode->llink = NULL;
	}
	else
	{
		DQ->front->llink = newnode;
		newnode->rlink = DQ->front;
		newnode->llink = NULL;
		DQ->front = newnode;
	}

}
//deleteFront 함수 구현하기.

element deleteRear(DQType* DQ)
{
	DQNode* old = DQ->rear;
	element item;
	if (isEmpty(DQ)) return 0;
	else
	{
		item = old->data;
		if (DQ->rear->llink = NULL)
		{
			DQ->front = NULL;
			DQ->rear = NULL;
		}
		else
		{
			DQ->rear = DQ->rear->llink;
			DQ->rear->rlink = NULL;
		}
		free(old);
		return item;
	}
}

element deleteFront(DQType* DQ)
{
	DQNode* old = DQ->front;
	element item;
	if (isEmpty(DQ)) return 0;
	else
	{
		item = old->data;
		if (DQ->front->rlink = NULL)
		{
			DQ->front = NULL;
			DQ->rear = NULL;
		}
	}
	free(old);
	return item;

}

element peekfront(DQType* DQ)
{
	element item;
	if (isEmpty(DQ)) return 0;
	else
	{
		item = DQ->front->data;
		return item;
	}
}

element peekrear(DQType* DQ)
{
	element item;
	if (isEmpty(DQ)) return 0;
	else
	{
		item = DQ->rear->data;
		return item;
	}
}

void display(DQType* DQ)
{
	DQNode* temp = DQ->front;
	printf("\n");
	while (temp)
	{
		printf("%3c", temp->data);
		temp = temp->rlink;
	}
	printf(")");
}
int isEmpty(DQType* DQ)
{
	if (DQ->front == NULL)
	{
		printf("값 없습니다!!1 \n");
		return 1;
	}
	else return 0;
}

int main()
{
	DQType* DQ1 = createDQue();
	element data;
	addFront(DQ1, 'A');
	addFront(DQ1, 'B');
	addRear(DQ1, 'C');
	display(DQ1);

	deleteFront(DQ1);
	deleteRear(DQ1);
	display(DQ1);

	getchar();

}