[백준(BOJ) / C][Silver Ⅳ] 10845번 : 큐

문제

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

10845번: 큐

---

풀이

해당 문제는 간단한 큐의 기능을 만드는 문제인데 저는 링크드 큐를 사용하여 문제를 해결하였습니다.

---

소스코드

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

// 노드 구조체
typedef struct tag_Node
{
	int data;
	struct tag_Node* nextnode;
} Node;

// 노드들을 관리하는 큐 구조체
typedef struct queue_list
{
	Node* frontnode;
	Node* rearnode;
	int size;
} List;

// 노드들을 관리하는 큐를 만듬
void CreateQueue(List** Queue);
// 큐에 새 노드를 삽입
void Enqueue(List* Queue, Node* NewNode);
// 큐에 노드를 제거하고 해당 값을 반환
int Dequeue(List* Queue);
// 큐에 노드가 있는지 확인하고 있다면 0 없다면 1 반환
int EmptyQueue(List* Queue);
// 노드를 생성
Node* CreateNode(int _data);
// 전위에 있는 노드를 반환
int FrontQueue(List* Queue);
// 후위에 있는 노드를 반환
int RearQueue(List* Queue);

int main(void)
{
	List* queue = NULL;
	Node* popped = NULL;
	
	int cmdcnt;
	char cmd[6];
	
	// 관리할 큐를 동적할당으로 공간을 만듬
	CreateQueue(&queue);
	
	scanf("%d", &cmdcnt);
	
	// cmdcnt만큼 명령어를 받는다.
	for(int i = 0; i < cmdcnt; i++)
	{
		scanf("%s", cmd);
		// C에서 문자열을 비교할때는 strcmp를 사용한다.
		if(!strcmp(cmd,"push"))
		{
			int num;
			scanf("%d", &num);
			
			Enqueue(queue, CreateNode(num));
		}
		else if(!strcmp(cmd,"front"))
		{
			printf("%d\n", FrontQueue(queue));
		}
		else if(!strcmp(cmd,"back"))
		{
			printf("%d\n", RearQueue(queue));
		}
		else if(!strcmp(cmd,"pop"))
		{
			printf("%d\n", Dequeue(queue));
		}
		else if(!strcmp(cmd,"size"))
		{
			printf("%d\n", queue->size);
		}
		else if(!strcmp(cmd,"empty"))
		{
			printf("%d\n", EmptyQueue(queue));
		}
	}
	
    free(queue);
    
	return 0;
}

// 노드들을 관리하는 큐를 만듬
void CreateQueue(List** Queue)
{
	// 동적할당으로 공간을 만들고 해당 큐의 값을들 초기화 한다.
	(*Queue) = (List*)malloc(sizeof(List));
	(*Queue)->frontnode = NULL;
	(*Queue)->rearnode = NULL;
	(*Queue)->size = 0;
}

// 큐에 새 노드를 삽입
void Enqueue(List* Queue, Node* NewNode)
{
	// 만약 큐의 전위노드가 없다면 
	if(Queue->frontnode == NULL)
	{
		// 전위 노드가 없다는 것은 큐에 아무런 값도 없다는 뜻이므로 전위, 후위노드에 새로운 노드를 추가한다.
		// 노드가 늘어났으므로 size에 1를 더한다.
		Queue->frontnode = NewNode;
		Queue->rearnode = NewNode;
		Queue->size++;
	}
	// 만약 큐의 전위노드가 있다면
	else
	{
		// 그럼 새로운 노드는 후위 노드 뒤에 들어가므로 현재 후위 노드의 다음 노드를 새노드로 바꾼다.
		Queue->rearnode->nextnode = NewNode;
		// 그리고 새 노르를 새로운 후위 노드로 설정한다.
		Queue->rearnode = NewNode;
		// 노드가 늘어났으므로 size에 1를 더한다.
		Queue->size++;
	}
}

// 큐에 노드를 제거하고 해당 값을 반환
int Dequeue(List* Queue)
{
	// 만약 전위노드가 없으면 현재 큐 안에 노드가 없으므로 -1를 반환한다.
	if(Queue->frontnode == NULL) return -1;
	
	// 현재 전위 노드를 저장할 변수를 선언하고 값을 넣는다.
	Node* front = Queue->frontnode;
	// 반환할 전위 노드의 data값을 넣는다.
	int _data = front->data;
    
	// 현재 전위노드의 다음 노드가 없다면 
	if(Queue->frontnode->nextnode == NULL)
	{
		// 다음 노드가 없다는것은 해당 전위노드가 사라진다면 큐에는 노드가 남아있지않다는 뜻이므로 후위 노드까지 초기화해준다.
		Queue->frontnode = NULL;
		Queue->rearnode = NULL;
	}
	// 현재 전위노드의 다음 노드가 있다면
	else
	{
		// 다음 전위노드를 현재 전위노드의 다음 노드로 넣어준다.
		Queue->frontnode = Queue->frontnode->nextnode;
	}
	
	Queue->size--;
	free(front);
	
	return _data;
}

int EmptyQueue(List* Queue)
{
	return (Queue->frontnode == NULL);
}

Node* CreateNode(int _data)
{
	Node* NewNode = (Node*)malloc(sizeof(Node));
	
	NewNode->data = _data;
	NewNode->nextnode = NULL;
	
	return NewNode;
}

int FrontQueue(List* Queue)
{
	return Queue->frontnode == NULL ? -1 : Queue->frontnode->data; 
}

int RearQueue(List* Queue)
{
	return Queue->rearnode == NULL ? -1 : Queue->rearnode->data;
}