백준 10845 큐 C++

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

예제 출력 1

1
2
2
0
1
2
-1
0
1
-1
0
3

출처

• 문제를 만든 사람: baekjoon
• 문제의 오타를 찾은 사람: compro0317

알고리즘 분류

• 자료 구조
• 큐

 

풀이

큐는 선입선출(First In First Out; FIFO)의 자료구조이다. 대기열이라고도 한다.

데이터가 들어오는 위치는 가장 뒤(Rear 또는 Back)에 있고, 데이터가 나가는 위치는 가장 앞(Front)에 있다.

먼저 들어오는 데이터가 먼저 나가게 된다.

우선순위 큐, 원형 큐 등의 베리에이션이 존재한다.

입력 동작은 Enqueue(Push), 출력 동작은 Dequeue(Pop)라고 한다.

 

큐의 구현

배열 사용 시 Enqueue, Dequeue 반복에 따라 데이터가 앞으로 밀려나므로 원형 버퍼로 해결하는 경우가 있다.

연결리스트 사용

 

이 문제에서는 배열로 구현하였다.

push를 할 때에는 cur의 위치를 뒤로 이동하였다.

pop을 할 때에는 첫번째 데이터를 출력하고 나머지 데이터를 한 칸씩 앞으로 옮기고 마지막 데이터는 Null 처리 했다.

 

코드

#include <iostream>
#include <string>
using namespace std;

class queue {
	int cur;

public:
	int arr[10001];
	queue() {
		cur = -1;
	}

	void push(int x) {
		arr[++cur] = x;
	}

	int pop() {
		if (empty()) {
			return -1;
		}
		else {
			int result;
			result = arr[0];
			for (int i = 0; i < cur; i++) {
				arr[i] = arr[i + 1];
			}
			arr[cur] = NULL;
			cur--;
			return result;
		}
	}

	int size() {
		return (cur + 1);
	}

	int empty() {
		return (cur == -1);
	}

	int front() {
		if (empty()) {
			return -1;
		}
		return arr[0];
	}

	int back() {
		if (empty()) {
			return -1;
		}
		return arr[cur];
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//make queue that save integers

	int n;
	string input;
	queue q;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> input;
		if (input == "push") {
			int m;
			cin >> m;
			q.push(m);
		}
		else if (input == "pop") {
			cout << q.pop() << '\n';
		}
		else if (input == "size") {
			cout << q.size() << '\n';
		}
		else if (input == "empty") {
			cout << q.empty() << '\n';
		}
		else if (input == "front") {
			cout << q.front() << '\n';
		}
		else if (input == "back") {
			cout << q.back() << '\n';
		}
	}
}