<백준 알고리즘> 10866번: 덱

문제

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1

15 push_back 1 push_front 2 front back size empty pop_front pop_back pop_front size empty pop_back push_front 3 empty front

예제 출력 1

2 1 2 0 2 1 -1 0 1 -1 0 3

예제 입력 2

22 front back pop_front pop_back push_front 1 front pop_back push_back 2 back pop_front push_front 10 push_front 333 front back pop_back pop_back push_back 20 push_back 1234 front back pop_back pop_back

예제 출력 2

-1 -1 -1 -1 1 1 2 2 333 10 10 333 20 1234 1234 20

---

Solution

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

typedef int element;
typedef struct DlistNode
{
	element data;
	struct DlistNode *llink;
	struct DlistNode *rlink;
}
DlistNode;

void init(DlistNode *phead)
{
	phead->llink=phead;
	phead->rlink=phead;
	phead->data=-1;
}

void push_front(DlistNode *before,DlistNode *new_node)
{
	while(before->llink->data!=-1)
		before=before->llink;

	new_node->llink=before->llink;
	new_node->rlink=before;

	before->llink->rlink=new_node;
	before->llink=new_node;
}

void push_back(DlistNode *before,DlistNode *new_node)
{
	while(before->rlink->data!=-1)
		before=before->rlink;

	new_node->llink=before;
	new_node->rlink=before->rlink;

	before->rlink->llink=new_node;
	before->rlink=new_node;
}

void dremove_node(DlistNode *phead_node,DlistNode *removed)
{
	if(removed==phead_node)
		return;

	removed->llink->rlink=removed->rlink;
	removed->rlink->llink=removed->llink;

	free(removed);
}

int pop_front(DlistNode *phead_node)
{
	int N=phead_node->rlink->data;

	dremove_node(phead_node,phead_node->rlink);
	return N;
}

int pop_back(DlistNode *phead_node)
{
	int N=phead_node->llink->data;

	dremove_node(phead_node,phead_node->llink);
	return N;
}

int front(DlistNode *phead_node)
{
	return phead_node->rlink->data;
}

int back(DlistNode *phead_node)
{
	return phead_node->llink->data;
}

int main(void)
{
	DlistNode head_node, **deque=NULL;
	int N, size=0, num;

	scanf("%d", &N);
	while(getchar()!='\n');

	deque=(DlistNode **)malloc(sizeof(DlistNode *)*N);
	init(&head_node);

	for(int i=0;i<N;i++)
	{
		char command[30]={'\0', };

		fgets(command,sizeof(command),stdin);
		deque[i]=(DlistNode *)malloc(sizeof(DlistNode));

		if(strncmp(command,"push_front",10)==0)
		{
			for(int j=11;command[j]!='\0';j++)
				command[j-11]=command[j];

			deque[i]->data=atoi(command);
			push_front(&head_node,deque[i]);
			size++;
		}
		else if(strncmp(command,"push_back",9)==0)
		{
			for(int j=10;command[j]!='\0';j++)
				command[j-10]=command[j];

			deque[i]->data=atoi(command);
			push_back(&head_node,deque[i]);
			size++;
		}
		else if(strncmp(command,"pop_front",9)==0)
		{
			num=pop_front(&head_node);
			printf("%d\n", num);
			free(deque[i]);
			size-=num!=-1;
		}
		else if(strncmp(command,"pop_back",8)==0)
		{
			num=pop_back(&head_node);
			printf("%d\n", num);
			free(deque[i]);
			size-=num!=-1;
		}
		else if(strncmp(command,"size",4)==0)
		{
			printf("%d\n", size);
			free(deque[i]);
		}
		else if(strncmp(command,"front",5)==0)
		{
			printf("%d\n", front(&head_node));
			free(deque[i]);
		}
		else if(strncmp(command,"back",4)==0)
		{
			printf("%d\n", back(&head_node));
			free(deque[i]);
		}
		else if(strncmp(command,"empty",5)==0)
		{
			printf("%d\n", size==0);
			free(deque[i]);
		}
		else
		{
			printf("error\n");
			free(deque[i]);
		}
	}

	return 0;
}