10866: 덱

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

10866번: 덱

 

덱(deque)은 큐이지만 양방향으로 원소를 넣고 뺄 수 있는 자료구조이다. 이 문제는 그 덱을 구현만 하는 문제이다.

 

덱은 양방향이므로 양방향으로 왔다갔다 할 수 있는 이중 연결리스트를 사용하기로 했다.

 

 

문제가 문자열로 입력을 받아야했는데 문자열 문법을 다 까먹어서..ㅎㅎㅎ 구글링으로 문자열에 대해 다시 좀 공부했다.

strlen(a) : a의 길이
strcat(a,b) : a뒤에 b붙이기	strncat(a,b,n) : a뒤에 b의 앞부분 n만큼만 붙이기
strcpy(a,b) : a에 b복사하기	strncpy(a,b,n) : a의 앞부분 중 n만큼에 b의 앞부분 n만큼만 복사하기
strcmp(a,b) : a와 b비교 같으면 0, a가 b보다 크면 >0, b가 a보다 크면 <0	strncmp(a,b,n) : a와 b의 앞 n만큼만 비교   *여기에서 크다는 것은 사전순으로 더 뒤에 있다는 의미

 

이 정도의 문자열 함수를 다시 봤고 문자열은 띄어쓰기를 입력할 수 없다는 것도 까먹었었다;;

 

문자열로 입력을 받고 정수입력이 필요한 함수인 push_front, push_back if문 안에서 정수 입력을 받았다. 그리고 모두 함수로 만들어서 출력을 했다.

 

#pragma warning (disable : 4996)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct NODE{
	int elem;
	struct NODE* next, * prev;
}NODE;

void push_front(NODE* H,int elem);
void push_back(NODE* T, int elem);
int pop_front(NODE* H, NODE* T);
int pop_back(NODE* H, NODE* T);
int size(NODE* H, NODE* T);
int empty(NODE* H, NODE* T);
int front(NODE* H, NODE* T);
int back(NODE* H, NODE* T);

int main() {
	int N, i, X;
	char cmd[11] = "";
	scanf("%d", &N);

	NODE* H, * T;
	H = (NODE*)malloc(sizeof(NODE));
	T = (NODE*)malloc(sizeof(NODE));
	H->elem = -1;
	T->elem = -1;
	H->next = T;
	H->prev = H;
	T->prev = H;
	T->next = T;

	for (i = 0; i < N; i++) {
		getchar();
		scanf("%s", cmd);
		if (strcmp(cmd, "push_front")==0) {
			scanf("%d", &X);
			push_front(H, X);
		}
		else if (strcmp(cmd, "push_back") == 0) {
			scanf("%d", &X);
			push_back(T, X);
			NODE* p = H->next;
		}
		else if (strcmp(cmd, "pop_front") == 0) {
			printf("%d\n", pop_front(H,T));
		}
		else if (strcmp(cmd, "pop_back") == 0) {
			printf("%d\n", pop_back(H,T));
		}
		else if (strcmp(cmd, "size") == 0) {
			printf("%d\n", size(H, T));
		}
		else if (strcmp(cmd, "empty") == 0) {
			printf("%d\n", empty(H, T));
		}
		else if (strcmp(cmd, "front") == 0) {
			printf("%d\n", front(H, T));
		}
		else if (strcmp(cmd, "back") == 0) {
			printf("%d\n", back(H, T));
		}
	}
	return 0;
}
void push_front(NODE* H, int elem) {
	NODE* newnode = (NODE*)malloc(sizeof(NODE));
	newnode->elem = elem;
	NODE* p = H;
	newnode->next = p->next;
	newnode->prev = p;
	p->next->prev = newnode;
	p->next = newnode;
	return;
}
void push_back(NODE* T, int elem) {
	NODE* newnode = (NODE*)malloc(sizeof(NODE));
	newnode->elem = elem;
	NODE* p = T;
	newnode->next = p;
	newnode->prev = p->prev;
	p->prev->next = newnode;
	p->prev = newnode;
	return;
}
int pop_front(NODE* H,NODE*T) {
	if (empty(H,T) == 1) {
		return -1;
	}
	int elem;
	NODE* p = H, * q = H->next, * r = H->next->next;
	p->next = r;
	r->prev = p;
	elem = q->elem;
	free(q);
	return elem;
}
int pop_back(NODE*H,NODE* T) {
	if (empty(H,T) == 1) {
		return -1;
	}
	int elem;
	NODE* p = T, * q = T->prev, * r = T->prev->prev;
	p->prev = r;
	r->next = p;
	elem = q->elem;
	free(q);
	return elem;
}
int size(NODE* H, NODE* T) {
	int size = 0;
	NODE* p = H->next;
	while (p != T) {
		size++;
		p = p->next;
	}
	return size;
}
int empty(NODE* H,NODE*T) {
	if (H->next == T)return 1;
	return 0;
}
int front(NODE* H, NODE* T) {
	if (empty(H, T) == 1) {
		return -1;
	}
	NODE* p = H->next;
	return p->elem;
}
int back(NODE* H, NODE* T) {
	if (empty(H, T) == 1) {
		return -1;
	}
	NODE* p = T->prev;
	return p->elem;
}

 

이중연결리스트를 다룰줄만 알면 너무 간단하게 풀리는 문제였다.