[백준] 18258번: 큐 2 (C언어) - Linked List 이용하여 Queue 구현

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

18258번: 큐 2

 

 

난이도: solved.ac 실버 4

 

 

Linked List 복습 겸 Linked List를 이용해 큐(Queue)를 구현해 보았다

 

front, rear는 큐의 맨 앞, 맨 뒤를 가리키는 노드이다

 

front와 rear는 main 함수에서 둘 다 NULL이 되도록 초기화를 시켜준다

 

push 명령어는 어제 포스팅했던 스택 문제(10828번)를 풀 때처럼

 

push X(정수)를 push 따로, X 따로 입력받았다

 

https://jangkunstory.tistory.com/2

[백준] 10828번: 스택 (C언어)

 

push를 할 때, 새로운 노드를 생성해 그 노드의 next는 NULL로 만들어주고

 

새로운 노드의 data에 입력받은 정수를 저장하는데

 

그러고 나서 그 노드를 rear로 만들어준다

 

pop을 할 때는 front가 가리키는 노드가 원래의 front의 next가 가리키는 노드를 가리키도록 해주는데

 

pop을 하면서 큐에 정수가 들어있지 않게 되면 front의 next는 NULL이 되게 된다

 

push를 할 때 새로운 노드의 next는 NULL을 가리키고 pop을 하면서 모든 노드가 빠져나가게 되면 front가 그 NULL을 가리키게 되기 때문이다

 

큐를 복습하는 목적으로 빠른 시일 내에 배열(array)을 이용하여 큐를 다시 구현하고 포스팅해보겠다

 

(코드)

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

#define TRUE 1
#define FALSE 0
#define ERROR -1

/* Linked List */
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/* Queue */
typedef struct _linkedQueue {
	Node* front;
	Node* rear;
} Queue;

int num;	// Queue내 정수의 개수

void push(Queue*, int);
int pop(Queue*);
void size(Queue*);
int empty(Queue*);
int front(Queue*);
int back(Queue*);

int main() {
	int N, i, data;	// data: push일 때 입력받는 수
	char command[6];	// 입력 명령어를 담을 문자열
	Queue q;

	/* Queue 초기화 */
	q.front = NULL;
	q.rear == NULL;
	num = 0;

	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%s", command);
		if (!strcmp(command, "push")) {
			scanf("%d", &data);
			push(&q, data);
		}
		else if (!strcmp(command, "pop"))
			printf("%d\n", pop(&q));
		else if (!strcmp(command, "size"))
			size(&q);
		else if (!strcmp(command, "empty"))
			printf("%d\n", empty(&q));
		else if (!strcmp(command, "front"))
			printf("%d\n", front(&q));
		else if (!strcmp(command, "back"))
			printf("%d\n", back(&q));
	}

	return 0;
}

void push(Queue* pq, int data) {
	Node* newNode = (Node*)malloc(sizeof(Node));	// 새로운 노드 생성
	newNode->data = data;	// 새로운 노드에 입력받은 수를 넣음
	newNode->next = NULL;	// 새로운 노드가 가리키는 다음 노드는 NULL

	if (pq->front == NULL) {	// Queue가 비어있을 때
		pq->front = newNode;
		pq->rear = newNode;
	}
	else {
		pq->rear->next = newNode;
		pq->rear = newNode;
	}
	num++;	// Queue에 들어있는 정수의 개수 하나 증가
}

int pop(Queue* pq) {
	if (pq->front == NULL)	//	Queue가 비어있을 때
		return ERROR;
	else {
		Node* delNode;
		delNode = pq->front;
		int deldata = delNode->data;
		pq->front = pq->front->next;
		num--;	//	Queue에 들어있는 정수의 개수 하나 감소
		free(delNode);	// pop하는 Node의 메모리 해제
		return deldata;
	}
}

void size(Queue* pq) {
	printf("%d\n", num);
}

int empty(Queue* pq) {
	if (pq->front == NULL)	// Queue가 비어있을 때
		return TRUE;
	else
		return FALSE;
}

int front(Queue* pq) {
	if (pq->front == NULL)	// Queue가 비어있을 때
		return ERROR;
	else {
		int front_data = pq->front->data;
		return front_data;
	}
}

int back(Queue* pq) {
	if (pq->front == NULL)	// Queue가 비어있을 때
		return ERROR;
	else {
		int back_data = pq->rear->data;
		return back_data;
	}
}