[백준(BOJ) / C][Silver Ⅳ] 10866번 : 덱

문제

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

10866번: 덱

---

풀이

이중 연결 리스트(Doubly Linked List)로 구현하였고, 큐, 스택의 동작 방식을 참고하였습니다.

---

소스코드

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

typedef struct tag_node
{
	int data;
	struct tag_node* nextnode;
	struct tag_node* prevnode;
}Node;

typedef struct tag_list
{
	Node* frontnode;
	Node* rearnode;
	int size;
}List;

// 큐 초기화
void CreateQueue(List** _queue);
// 큐 제거
void DestroyQueue(List* _queue);

// 노드 생성
Node* CreateNode(int _data);
// 노드 제거
void DestroyNode(Node* _node);

// Front에 노드 삽입
void Push_Front(List* _queue, Node* _newnode);
// Back에 노드 삽입
void Push_Back(List* _queue, Node* _newnode);


// Front 노드 출력 후 제거
int Pop_Front(List* _queue);
// Back 노드 출력 후 제거
int Pop_Back(List* _queue);

// 큐 비어있는지 확인 
int Empty_Queue(List* _queue);


// Front 노드 출력
int Print_Front(List* _queue);
// Back 노드 출력
int Print_Back(List* _queue);

int main(void)
{
	List* queue = NULL;
	Node* current = NULL;
	int cmdcnt, num;
	char cmd[11];
	
	scanf("%d", &cmdcnt);
	
	CreateQueue(&queue);
	
	for(int i = 0; i < cmdcnt; i++)
	{
		scanf("%s", cmd);
		
		if(!strcmp(cmd, "push_front"))
		{
			scanf("%d", &num);
			Push_Front(queue, CreateNode(num));
		}
		else if(!strcmp(cmd, "push_back"))
		{
			scanf("%d", &num);
			Push_Back(queue, CreateNode(num));
		}
		else if(!strcmp(cmd, "pop_front"))
		{
			printf("%d\n", Pop_Front(queue));
		}
		else if(!strcmp(cmd, "pop_back"))
		{
			printf("%d\n", Pop_Back(queue));
		}
		else if(!strcmp(cmd, "size"))
		{
			printf("%d\n", queue->size);
		}
		else if(!strcmp(cmd, "empty"))
		{
			printf("%d\n", Empty_Queue(queue));
		}
		else if(!strcmp(cmd, "front"))
		{
			printf("%d\n", Print_Front(queue));
		}
		else if(!strcmp(cmd, "back"))
		{
			printf("%d\n", Print_Back(queue));
		}
	}
	
	
	return 0;
}

void CreateQueue(List** _queue)
{
	// queue가 사용할 메모리 공간을 할당 받은 후 초기화 합니다.
	(*_queue) = (List*)malloc(sizeof(List));
	(*_queue)->frontnode = NULL;
	(*_queue)->rearnode = NULL;
	(*_queue)->size = 0;
}

void DestroyQueue(List* _queue)
{
	free(_queue);
}

Node* CreateNode(int _data)
{
	// 새로운 노드가 사용할 메모리 공간을 할당 받고 초기화 합니다.
	Node* newNode = (Node*)malloc(sizeof(Node));
	
	newNode->nextnode = NULL;
	newNode->prevnode = NULL;
	newNode->data = _data;
	
	// 새로운 노드의 주소를 반환값으로 보냅니다.
	return newNode; 
}

void DestroyNode(Node* _node)
{
	free(_node);
}

void Push_Front(List* _queue, Node* _newnode)
{
	// 만약 queue의 frontnode가 없다면 queue가 비어있다는 뜻이므로 frontnode와 rearnode에 newnode를 넣습니다.
	if(_queue->frontnode == NULL)
	{
		_queue->frontnode = _newnode;
		_queue->rearnode = _newnode;
		_queue->size++;
	}
	// 만약 queue에 frontnode가 있다면 frontnode가 새로운 노드로 바뀌기 때문에
	// 새로운 노드의 nextnode를 현재 frontnode로, 현재 frontnode의 prevnode를 새로운 노드로 설정해줍니다.
	// 새로운 노드를 frontnode로 설정해줍니다.
	else
	{
		_newnode->nextnode = _queue->frontnode;
		_queue->frontnode->prevnode = _newnode;
		_queue->frontnode = _newnode;
		_queue->size++;
	}
}

void Push_Back(List* _queue, Node* _newnode)
{
	// 만약 queue의 rearnode가 없다면 queue가 비어있다는 뜻이므로 frontnode와 rearnode에 newnode를 넣습니다.
	if(_queue->rearnode == NULL)
	{
		_queue->frontnode = _newnode;
		_queue->rearnode = _newnode;
		_queue->size++;
	}
	// 만약 queue에 rearnode가 있다면 새로운 노드를 rearnode로 바꾸어야 하기 때문에
	// rearnode의 nextnode를 _newnode로 설정해 줍니다.
	// 새로운 노드의 prevnode는 현재 rearnode로 설정해줍니다.
	// 모든 연결이 끝났으면 새로운 노드를 rearnode로 설정해줍니다.
	else
	{
		_queue->rearnode->nextnode = _newnode;
		_newnode->prevnode = _queue->rearnode;
		_queue->rearnode = _newnode;
		_queue->size++;
	}
}

int Pop_Front(List* _queue)
{
	// 만약 frontnode가 없다면 -1 를 반환합니다.
	if(_queue->frontnode == NULL) 
	{
		return -1;
	}
	else
	{
		// 현재 frontnode의 주소를 저장하는 변수
		// 사용한 할당된 메모리를 해제하기 위해 저장.
		Node* _node = _queue->frontnode;
		// 현재 frontnode의 값을 저장하는 변수
		int _data = _node->data;
		
		// 만약 frontnode의 다음 노드가 없다면 마지막 노드라는 뜻(비어있다는 뜻)이기에 frontnode와 rearnode를 NULL 로 바꾸어줍니다.
		if(_queue->frontnode->nextnode == NULL)
		{
			_queue->frontnode = NULL;
			_queue->rearnode = NULL;
		}
		// 만약 frontnode의 다음 노드가 있다면
		else
		{
			// frontnode를 현재 frontnode의 nextnode로 바꾸어줍니다.
			_queue->frontnode = _queue->frontnode->nextnode;
			// 제일 앞으로 오게된 frontnode는 자신의 앞에 아무런 노드가 없으므로 prevnode를 NULL 으로 바꾸어줍니다.
			_queue->frontnode->prevnode = NULL;
		}
		
		_queue->size--;
		DestroyNode(_node);
		
		return _data;
	}
	
}

int Pop_Back(List* _queue)
{
	// 만약 rearnode가 없다면 -1 를 반환합니다.
	if(_queue->rearnode == NULL)
	{
		return -1;
	}
	else
	{
		// 현재 rearnode의 주소를 저장하는 변수
		// 사용한 할당된 메모리를 해제하기 위해 저장.
		Node* _node = _queue->rearnode;
		// 현재 rearnode의 값을 저장하는 변수
		int _data = _node->data;
		
		// 만약 rearnode의 이전 노드가 없다면 마지막 노드라는 뜻(비어있다는 뜻)이기에 frontnode와 rearnode를 NULL 로 바꾸어줍니다.
		if(_queue->rearnode->prevnode == NULL)
		{
			_queue->frontnode = NULL;
			_queue->rearnode = NULL;
		}
		// 만약 rearnode의 이전 노드가 있다면
		else
		{
			// rearnode를 현재 rearnode의 prevnode(이전 노드) 로 바꾸어줍니다.
			_queue->rearnode = _queue->rearnode->prevnode;
			// 제일 뒤로 오게된 rearndoe는 자신의 뒤에 아무런 노드가 없으므로 nextnode를 NULL 으로 바꾸어줍니다.
			_queue->rearnode->nextnode = NULL;
		}
		
		_queue->size--;
		DestroyNode(_node);
		
		return _data;
	}
}


int Empty_Queue(List* _queue)
{
	return _queue->frontnode == NULL ? 1 : 0;
}

int Print_Front(List* _queue)
{
	if(_queue->frontnode == NULL)
	{
		return -1;
	}
	else
	{
		return _queue->frontnode->data;
	}
}

int Print_Back(List* _queue)
{
	if(_queue->rearnode == NULL)
	{
		return -1;
	}
	else
	{
		return _queue->rearnode->data;	
	}
}