0x06 - 큐

FIFO의 선입선출 구조

큐의 성질

1. 원소의 추가제거가 O(1)

2. 제일 앞/뒤의 원소확인이 O(1)

3. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

연습문제

10845 . 큐

#include <bits/stdc++.h>

using namespace std;

int main()
{

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	queue <int> q;
	for (int i = 0; i < n; i++)
	{
		string command;

		cin >> command;

		if (command == "push")
		{
			int input;
			cin >> input;

			q.push(input);
		}
		else if (command == "pop")
		{
			if (q.empty())
			{
				cout << "-1\n";
			}
			else
			{
				cout << q.front() << '\n';
				q.pop();
			}
		}
		else if (command == "size")
		{
			cout << q.size() << '\n';
		}
		else if (command == "empty")
		{
			cout << q.empty() << '\n';
		}
		else if (command == "front")
		{
			if (q.empty())
			{
				cout << "-1\n";
			}
			else
			{
				cout << q.front() << '\n';
			}
		}
		else if (command == "back")
		{
			if (q.empty())
			{
				cout << "-1\n";
			}
			else
			{
				cout << q.back() << '\n';
			}
		}
	}
}

STL 큐의 멤버함수들을 활용해서 풀수있는 문제였다 pop,front 와 back의 경우 각 함수를 실행하기전에 empty를통해 큐가 비어있는지 미리 예외처리를 해주어야한다.

18528 .큐2

명령어의 갯수가 1만에서 20만으로 늘었다 STL큐와 endl사용금지와 cin.tie(0) 같은 기본을 지키면 시간을 초과하지않고 문제를 해결할수있다.

2164 . 카드 2

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;

	queue <int> q;
	cin >> n;
	for (size_t i = 1; i <= n; i++)
	{
		q.push(i);
	}

	while (q.size() != 1)
	{
		q.pop();
		q.push(q.front());
		q.pop();
	}
	cout << q.front();
}

1이 제일 위에있고 N이 제일 아래이기때문에 큐에 1~N까지의 숫자를 순서대로 push해준다.

다음 while문을 통해 q의 사이즈가 1일 될때까지 pop을 해주고 front를 푸쉬하고 팝해주는 동작을 반복한다 마지막으로 반복문을 탈출했을때는 큐에 카드한장이 남아있으니 front를 통해 출력해준다.