덱 (구조체로 구현)

덱 기본 설명

덱은 간단하게 생각해서 원형 큐를 조금 확장시킨 개념이라 생각할 수 있다. 원형 큐는 rear에서 enqueue를 하고 front에서 dequeue를 했지만, 덱은 여기서 확장해서 front과 rear 모두에서 enqueue와 dequeue를 한다고 생각하면 된다. 코드의 구현에 있어서 생각해야 할 것은, 원형 큐에서의 enqueue를 push_front와 push_back로 나누고, dequeue를 pop_front와 pop_back으로 나누고 코드를 잘 짜야한다는 것이다. 밑에서 설명할 함수들에 있는 full()함수와 empty()함수는 완성된 코드에 있다.

void enqueue(Queue* q, int data) 
{
	if (full(q))
	{
		printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n");
		return;
	}
	else 
	{
		q->rear = (q->rear + 1) % MAX;
		q->queue[q->rear] = data;
	}
}

void push_back(Deque* d, int data) 
{
	if(full(d))
	{
		printf("덱이 포화상태입니다. 데이터 삽입을 취소합니다.\n");
		return;
	}
	else
	{
		d->rear = (d->rear+1) % MAX;
		d->deque[d->rear] = data;
	}
}

원형 큐의 enqueue 함수와 덱의 push_back 함수다. 조금만 생각하면 push_back은 enqueue와 유사하다는 것을 알 수 있고(사실상 같다), push_front은 조금 다르게 짜야한다는 것을 알 수 있다. front에서의 데이터 삽입은 오른쪽에서 왼쪽으로 간다.

void push_front(Deque* d, int data) 
{
	if(full(d))
		printf("덱이 포화상태입니다. 데이터 삽입을 취소합니다.\n");
	else
	{
		d->deque[d->front] = data;
		d->front = (d->front-1+MAX) % MAX;	
	}
}

그러면 조금만 생각하면 pop_front은 push_front와의 반대 방향으로 데이터를 삭제해야하므로, 데이터 삭제가 왼쪽에서 오른쪽으로 가므로 push_back 함수와 유사한 구조를 갖는 것을 알 수 있고, pop_back은 push_front와 유사한 구조를 가져야한다는 사실을 알 수 있다.

int pop_front(Deque* d)
{
	if(empty(d))
		return -1;
	
	d->front=(d->front+1)%MAX;
	return d->deque[d->front];
}

int pop_back(Deque* d)
{
	if(empty(d))
		return -1;
	
	int tmp=d->deque[d->rear];
	d->rear=(d->rear-1+MAX)%MAX;
	return tmp;
}

이로써 이것들을 종합해서 원형 큐 구조체 구현의 코드에 조금만 덧붙이면 구조체로 덱 구현 코드가 완성된다.

덱 직접 입력 코드 구현

위에서 설명한 것과 다르게 백준 10866번 문제로 코드를 구현해서 size() 함수 때문에 네개의 함수에 size관련 문장이 하나 늘어났다.

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

#define MAX 10000

typedef struct Deque {
	int *deque;
	int front, rear, size;
}Deque;

void init_deque(Deque* d)
{
	d->deque = (int*)malloc(sizeof(int)*MAX);
	d->front=0;
	d->rear=0;
	d->size=0;
}

int size(Deque* d)
{
	return d->size;
}

int full(Deque* d)
{
	return ((d->rear+1)%MAX==d->front);
}

int empty(Deque* d)
{
	return (d->front == d->rear);
}

int front(Deque* d)
{
	if(empty(d))
		return -1;
	return d->deque[(d->front+1)%MAX];
}

int back(Deque* d)
{
	if(empty(d))
		return -1;
	return d->deque[d->rear];
}

void push_front(Deque* d, int data) 
{
	if(full(d))
		printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n");
	else
	{
		d->deque[d->front] = data;
		d->front = (d->front-1+MAX) % MAX;	
		d->size++;
	}
}

void push_back(Deque* d, int data) 
{
	if(full(d))
		printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n");
	else
	{
		d->rear = (d->rear+1) % MAX;
		d->deque[d->rear] = data;
		d->size++;
	}
}

int pop_front(Deque* d)
{
	if(empty(d))
		return -1;
	
	d->front=(d->front+1)%MAX;
	d->size--;
	return d->deque[d->front];
}

int pop_back(Deque* d)
{
	if(empty(d))
		return -1;
	
	int tmp=d->deque[d->rear];
	d->rear=(d->rear-1+MAX)%MAX;
	d->size--;
	return tmp;
}

int main(void) 
{
	Deque* deque=(Deque*)malloc(sizeof(Deque));
	init_deque(deque);
	char Get_Com[11];
	int N,num;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		scanf("%s",Get_Com);
		if(strcmp(Get_Com,"push_front")==0)
		{
			scanf("%d",&num);
			push_front(deque,num);
		}
		else if(strcmp(Get_Com,"push_back")==0)
		{
			scanf("%d",&num);
			push_back(deque,num);
		}
		else if(strcmp(Get_Com,"front")==0)
			printf("%d\n",front(deque));
		else if(strcmp(Get_Com,"back")==0)
			printf("%d\n",back(deque));
		else if(strcmp(Get_Com,"empty")==0)
			printf("%d\n",empty(deque));
		else if(strcmp(Get_Com,"size")==0)
			printf("%d\n",size(deque));
		else if(strcmp(Get_Com,"pop_front")==0)
			printf("%d\n",pop_front(deque));
		else if(strcmp(Get_Com,"pop_back")==0)
			printf("%d\n",pop_back(deque));
	}
	return 0;
}