[백준/BOJ] 18258번 큐 2 (C/C++)

백준 온라인 저지(BOJ) 18258번 큐 2

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

18258번: 큐 2

* 사용언어 : C언어, C++

 

1. 문제

정수를 저장하는 큐를 구현하고, 입력으로 주어지는 명령을 처리

 

2. 풀이

메모리 제한이 넉넉하기 때문에 크기가 2,000,000인 1차원 배열을 선언하여 구현했습니다.

push나 pop을 할 때 큐에 있는 값들을 옮기지 않고,

head와 tail을 index로 저장해두고 그 값만 1 증가 or 1 감소해주는 방식입니다.

이렇게 구현할 경우 모든 명령의 시간 복잡도가 O(1)이 됩니다.

 

그 외 풀이는 아래 코드로 설명 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
18258_큐 2
8924KB	516ms
*/
#include <cstdio>

const int LM = 2000000;
int q[LM], h, t = -1, N, x;
char o[6];

int isEmpty() { return h > t; }

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	while (N--) {
		scanf("%s", o);

		if (o[0] == 'p') {
			if (o[1] == 'u') {
				scanf("%d", &x);
				q[++t] = x;
			}
			else printf("%d\n", isEmpty() ? -1 : q[h++]);
		}
		else if (o[0] == 's') printf("%d\n", t - h + 1);
		else if (o[0] == 'e') printf("%d\n", isEmpty());
		else if (o[0] == 'f') printf("%d\n", isEmpty() ? -1 : q[h]);
		else printf("%d\n", isEmpty() ? -1 : q[t]);
	}
	return 0;
}