백준 10845(큐) c언어

문제

10845번: 큐

자료구조 큐를 구현하는 문제입니다.

c언어로 작성했는데 c언어로 하나하나 직접 구현해보면 큐를 이해하는데 도움이 많이 됩니다.

코드를 보겠습니다.

---

int queue[10001];
int cnt = 0;
int front = 0;
int main() {
	int n;
	scanf("%d", &n);

	while (n--) {
		char ch[10];
		scanf("%s", &ch);

		if (strcmp(ch, "push")==0) {
			int a;
			scanf("%d", &a);
			push(a);
		}
		else if (strcmp(ch, "empty")==0) {
			if (empty())
				printf("1\n");
			else printf("0\n");
		}
		else if (strcmp(ch, "pop") == 0) {
			if (empty())
				printf("-1\n");
			else pop();
		}
		else if (strcmp(ch, "front") == 0) {
			if (empty())
				printf("-1\n");
			else printf("%d\n", queue[front]);
		}
		else if (strcmp(ch, "back") == 0) {
			if (empty())
				printf("-1\n");
			else printf("%d\n", queue[cnt - 1]);
		}
		else if (strcmp(ch, "size") == 0) {
			printf("%d\n", cnt-front);
		}
	}


	return 0;
}

queue라는 배열을 전역변수로 설정하였습니다. 나중에 push나 pop 같은 함수를 사용하기 위함입니다.

cnt변수는 큐에 들어갈 인덱스를 나타내줍니다. front변수는 큐의 앞부분을 가리켜 줍니다.

앞서 백준 스택문제와 매우 유사하지만 front라는 변수를 두어 큐의 앞부분에 접근하는 것만 잘 구현해주면 어렵지 않게 풀 수 있습니다.

나머지 함수들의 유사한 부분은 스택과 비슷하므로 여기를 보시면 이해가 가실겁니다.

---

pop 함수

void pop() {
	printf("%d\n", queue[front]);
	queue[front] = 0;
	front++;

}

front는 처음에 0의 값을 가집니다. 따라서 만약에 pop함수를 사용하면 queue[0]이 제거되므로 

queue[0] = 0으로 만들고 front의 값을 1더해주어 큐의 앞부분을 다시 의미하게됩니다.

그러므로 quque[front] = queue[1] 이 되어 새로운 front를 설정하게 됩니다.

---

size 함수

else if (strcmp(ch, "size") == 0) {
			printf("%d\n", cnt-front);
		}

큐의 사이즈를 구할때 cnt값에서 front를 빼줍니다. 

cnt는 맨뒤를 가리키고 front는 맨앞을 가리키므로 queue의 size가 나옵니다.

 

나머지 함수들은 stack과 동일합니다.

---

전체코드 입니다.

#include<stdio.h>
#include<string.h>
void push(int a);
int empty();
void pop();
int queue[10001];
int cnt = 0;
int front = 0;
int main() {
	int n;
	scanf("%d", &n);

	while (n--) {
		char ch[10];
		scanf("%s", &ch);

		if (strcmp(ch, "push")==0) {
			int a;
			scanf("%d", &a);
			push(a);
		}
		else if (strcmp(ch, "empty")==0) {
			if (empty())
				printf("1\n");
			else printf("0\n");
		}
		else if (strcmp(ch, "pop") == 0) {
			if (empty())
				printf("-1\n");
			else pop();
		}
		else if (strcmp(ch, "front") == 0) {
			if (empty())
				printf("-1\n");
			else printf("%d\n", queue[front]);
		}
		else if (strcmp(ch, "back") == 0) {
			if (empty())
				printf("-1\n");
			else printf("%d\n", queue[cnt - 1]);
		}
		else if (strcmp(ch, "size") == 0) {
			printf("%d\n", cnt-front);
		}
	}


	return 0;
}
void push(int a) {
	queue[cnt++] = a;
}
int empty() {
	if (cnt ==front)
		return 1;
	else return 0;
}
void pop() {
	printf("%d\n", queue[front]);
	queue[front] = 0;
	front++;

}