[C] 백준 10866

https://www.acmicpc.net/problem/10866

10866번: 덱

 

연결리스트가 생각이 안나서 배열로 덱을 구현했다. 

주어지는 명령의 수가 10000이기 때문에 덱에는 최대 10000개의 데이터가 들어갈 수 있다. 

 

이처럼 덱의 최대 크기가 정해져 있기에 원형덱으로 문제를 풀 수 있었다.

최대 크기가 정해져 있지 않다면 연결리스트로 푸는 편이 좋다. 

 

front와 back으로 크기를 구하는게 까다로울 것 같아서

deque 구조체에 size라는 변수를 선언하여 덱의 크기를 따로 관리하였다. 

 

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

typedef struct
{
	int front;
	int back;
	int size;
	int arr[10000];
} deque;

void init(deque* pq)
{
	pq->front = 0;
	pq->back = 9999;
	pq->size = 0;
}

void push_front(deque* pq, int data)
{
	pq->front--;
	if (pq->front < 0)
		pq->front = 9999;
	pq->arr[pq->front] = data;

	pq->size++;
}

void push_back(deque* pq, int data)
{
	pq->back++;
	if (pq->back > 9999)
		pq->back = 0;
	pq->arr[pq->back] = data;

	pq->size++;
}

void pop_front(deque* pq)
{
	if (pq->size == 0)
		printf("-1\n");
	else
	{
		printf("%d\n", pq->arr[pq->front]);
		pq->front++;
		if (pq->front == 10000)
			pq->front = 0;

		pq->size--;
	}
}

void pop_back(deque* pq)
{
	if (pq->size == 0)
		printf("-1\n");
	else
	{
		printf("%d\n", pq->arr[pq->back]);
		pq->back--;
		if (pq->back == -1)
			pq->back = 9999;

		pq->size--;
	}
}

void empty(deque* pq)
{
	if (pq->size == 0)
		printf("1\n");
	else
		printf("0\n");
}

void size(deque* pq)
{
	printf("%d\n", pq->size);
}

void front(deque* pq)
{
	if (pq->size == 0)
		printf("-1\n");
	else
		printf("%d\n", pq->arr[pq->front]);
}

void back(deque* pq)
{
	if (pq->size == 0)
		printf("-1\n");
	else
		printf("%d\n", pq->arr[pq->back]);
}

deque myqueue;

int main()
{
	char str[20];
	int n, data;
	scanf("%d", &n);

	init(&myqueue);

	for (int i = 0; i < n; i++)
	{
		scanf("%s", str);

		if (strcmp(str, "push_front") == 0)
		{
			scanf("%d", &data);
			push_front(&myqueue, data);
		}
		else if (strcmp(str, "push_back") == 0)
		{
			scanf("%d", &data);
			push_back(&myqueue, data);
		}
		else if (strcmp(str, "pop_front") == 0)
		{
			pop_front(&myqueue);
		}
		else if (strcmp(str, "pop_back") == 0)
		{
			pop_back(&myqueue);
		}
		else if (strcmp(str, "size") == 0)
		{
			size(&myqueue);
		}
		else if (strcmp(str, "empty") == 0)
		{
			empty(&myqueue);
		}
		else if (strcmp(str, "front") == 0)
		{
			front(&myqueue);
		}
		else if (strcmp(str, "back") == 0)
		{
			back(&myqueue);
		}
	}

	return 0;
}