BOJ 10866 : 덱 with Linked List

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/10866

 

참고

- BOJ 10866 : 덱

- 메모리 풀 Memory Pool

- 링크드 리스트 Linked List

- 링크드 리스트 Linked List Tail ver

- BOJ 13546 : 수열과 쿼리 4

 

 

배열로 구현했던 덱(deque)을 링크드 리스트를 이용해서 구현해보자.

 

구조체를 이용하여 DEQUE을 아래와 같이 정의한다.

값을 저장할 value와 앞과 뒤를 연결할 포인터를 선언한다.

그리고 최초로 사용할 deque와 front, back 포인터를 선언하고 메모리 풀을 적절히 잡는다.

typedef struct st
{
	int value;
	struct st* next;
	struct st* prev;
}DEQUE;

DEQUE deque;
DEQUE* front;
DEQUE* back;
DEQUE POOL[10000 + 100];
int pcnt;

 

배열에서는 back - front로 덱의 사이즈를 알 수 있었지만, 링크드 리스트는 불가능하므로,

deque의 크기는 전역변수로 따로 관리한다.

int dequeSize;

 

배열에서는 front는 먼저 앞으로 이동한 후, 값을 저장하였고, back은 값을 저장한 후에 뒤로 이동하였다.

if (mystrcmp(str, "push_front") == 0)
{
	scanf("%d", &input);
	deque[--front] = input;
}
else if (mystrcmp(str, "push_back") == 0)
{
	scanf("%d", &input);
	deque[back++] = input;
}

 

최초의 front와 back은 deque의 주소를 가리킨다.

front = back = &deque;

 

그러면 push_front는 아래와 같다.

사이즈를 증가시키고, node를 할당받은 후, node에 값을 저장한다.

그리고 node의 next가 front가 되도록 하고, front의 prev가 node를 가르키게 한 후,

front를 node로 이동시키면 위의 배열과 같은 구현이 된다.

void push_front(int value)
{
	dequeSize++;
	DEQUE* node = &POOL[pcnt++];
	node->value = value;

	node->next = front;
	front->prev = node;

	front = node;
}

 

back에 저장하는 방법은 다음과 같다.

값을 현재의 back에 저장시킨 후, node를 만들어서 뒤로 보내고 back을 node로 옮긴다.

void push_back(int value)
{
	dequeSize++;

	DEQUE* node = &POOL[pcnt++];
	
	back->value = value;
	
	node->prev = back;
	back->next = node;

	back = node;
}

이 방법대로면 back의 값을 출력하려면 back->prev->value가 된다.

 

따라서 pop_back은 아래와 같이 구현된다.

int pop_back()
{
	if (dequeSize == 0) return -1;

	dequeSize--;

	int ret = back->prev->value;

	back = back->prev;

	return ret;
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

int N;

typedef struct st
{
	int value;
	struct st* next;
	struct st* prev;
}DEQUE;

DEQUE deque;
DEQUE* front;
DEQUE* back;
DEQUE POOL[10000 + 100];
int pcnt;

int dequeSize;

void push_front(int value)
{
	dequeSize++;
	DEQUE* node = &POOL[pcnt++];
	node->value = value;

	node->next = front;
	front->prev = node;

	front = node;
}

void push_back(int value)
{
	dequeSize++;

	DEQUE* node = &POOL[pcnt++];
	
	back->value = value;
	
	node->prev = back;
	back->next = node;

	back = node;
}

int pop_front()
{
	if (dequeSize == 0) return -1;

	dequeSize--;

	int ret = front->value;

	front = front->next;

	return ret;
}

int pop_back()
{
	if (dequeSize == 0) return -1;

	dequeSize--;

	int ret = back->prev->value;

	back = back->prev;

	return ret;
}

int mystrcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

int main(void)
{
	int input;
	char str[15];

	scanf("%d", &N);

	front = back = &deque;
	for (int i = 0; i < N; i++)
	{
		scanf("%s", str);

		if (mystrcmp(str, "push_front") == 0)
		{
			scanf("%d", &input);
			push_front(input);
		}
		else if (mystrcmp(str, "push_back") == 0)
		{
			scanf("%d", &input);
			push_back(input);
		}
		else if (mystrcmp(str, "pop_front") == 0)
			printf("%d\n", pop_front());
		else if (mystrcmp(str, "pop_back") == 0)
			printf("%d\n", pop_back());
		else if (mystrcmp(str, "size") == 0)
			printf("%d\n", dequeSize);
		else if (mystrcmp(str, "empty") == 0)
			printf("%d\n", (dequeSize == 0) ? 1 : 0);
		else if (mystrcmp(str, "front") == 0)
			printf("%d\n", (dequeSize != 0) ? front->value : -1);
		else if (mystrcmp(str, "back") == 0)
			printf("%d\n", (dequeSize != 0) ? back->prev->value : -1);
	}

	return 0;
}