[C] 백준 | 10866번 코드 - 덱

>문제

> 핵심

덱

연결리스트

>풀이과정

처음엔 이 문제를 보고 이건 큐인가,, 스택인가,, 고민하다가

그냥 헤더 하나 만들어 놓고 연결리스트를 이어놓으면 다 되겠구나! 싶어서 연결리스트 방식으로 문제를 풀었다.

 

명령어가 워낙 많아서 코드가 엄~청 길어졌다.

손이 바쁘다 바빠

 

그나저나 다 풀고 나니까 덱이 뭔지 알았다.

덱(Deque)는 "double-ended queue" 의 줄임말으로 양쪽에 끝이 있는 큐라는 의미이다.

큐의 앞에서도 삽입/삭제, 뒤에서도 삽입/삭제가 모두 가능한 구조.

스택이면서 동시에 큐 같은 느낌?

 

이미지 : https://iq.opengenus.org/deque-in-cpp-stl/

아무튼 이 deque에서는 문제에 나온것 처럼 네가지 명령을 기본적으로 수행한다

 

· push_front   (->addLast)

· push_back   (->addFirst)

· pop_front    (->deleteLast)

· pop_back    (->deleteFirst)

 

원형 큐로도 구현을 할 수 있다고 하는데 솔직히 연결리스트를 배운 입장에서 그냥 연결리스트를 이용하는게 훨씬 나을 것 같다는 생각이 든다..

어디가 front고 어디가 back인지 좀 헷갈렸는데 헤더 바로 앞을 back, 제일 끝쪽을 front로 둔다. 스택을 생각하면 될듯.

 

연결리스트와 단 하나의 차이가 있다면 연결리스트는 연결 중간에 노드를 삽입/삭제 하기도 하는데 이건 단순히 양쪽 끝단에서만 삽입/삭제를 한다는 점?

그리고 삭제연산을 하기 위해서 이중연결리스트로 구현을 하는게 정신건강에 좋을 것 같다. (free 및 NULL 처리를 위해..)

 

>깨달은점

연결리스트는 어려웡

덱은 이중연결리스트로 구현하자

 

>코드

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

#define SIZE 10001

typedef struct node
{
	struct node* next;
	struct node* prev;
	int key;
}node;

void getNode(node** p)
{
	(*p) = (node*)malloc(sizeof(node));
	(*p)->next = NULL;
	(*p)->prev = NULL;
}

void push_front(node* H, int e) // addLast
{
	node* p = NULL; getNode(&p); 
	p->key = e;

	node* q = H; 
	while (q->next != NULL) 
		q = q->next;

	p->prev = q;
	q->next = p;
}

void push_back(node* H, int e) // addFirst
{
	node* p = NULL; getNode(&p);
	p->key = e;

	p->next = H->next;
	p->prev = H;
	if (H->next != NULL) H->next->prev = p;
	H->next = p;
}

int pop_front(node* H) // deleteLast
{
	if (H->next == NULL)
		return -1;

	node* p = H; while (p->next != NULL) p = p->next;
	int tmp = p->key;
	p = p->prev;

	free(p->next);
	p->next = NULL;

	return tmp;
}

int pop_back(node* H) // deleteFirst
{
	if (H->next == NULL)
		return -1;

	node* p = H->next;
	int tmp = p->key;
	H->next = p->next;
	if (p->next != NULL) p->next->prev = H;
	free(p);

	return tmp;
}

void print(node* H)
{
	node* p = H->next;
	while (p != NULL)
	{
		printf("[%d] ", p->key);
		p = p->next;
	}
	printf("\n");
}

int is_empty(node* H)
{
	return (H->next == NULL);
}

int front(node* H)
{
	if (is_empty(H))
		return -1;
	node* p = H; while (p->next != NULL)p = p->next;
	return p->key;
}

int back(node* H)
{
	if (is_empty(H))
		return -1;
	else
		return H->next->key;
}

int main()
{
	node *H = NULL; getNode(&H);

	int i, n, e, size = 0;
	char op[15];

	scanf("%d", &n);

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

		if (strcmp(op, "push_front") == 0)
		{
			scanf(" %d", &e);
			push_front(H, e);
			size += 1;
		}
		else if (strcmp(op, "push_back") == 0)
		{
			scanf(" %d", &e);
			push_back(H, e);
			size += 1;
		}
		else if (strcmp(op, "pop_front") == 0)
		{
			e = pop_front(H);
			printf("%d\n", e);
			if (e != -1)
				size -= 1;
		}
		else if (strcmp(op, "pop_back") == 0)
		{
			e = pop_back(H);
			printf("%d\n", e);
			if (e != -1)
				size -= 1;
		}
		else if (strcmp(op, "size") == 0)
		{
			printf("%d\n", size);
		}
		else if (strcmp(op, "empty") == 0)
		{
			e = is_empty(H);
			printf("%d\n", e);
		}
		else if (strcmp(op, "front") == 0)
		{
			e = front(H);
			printf("%d\n", e);
		}
		else if (strcmp(op, "back") == 0)
		{
			e = back(H);
			printf("%d\n", e);
		}
	}

	return 0;
}