#4 코테준비 - 큐(Queue)

큐(Queue)

- 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄수있는 자료구조

(FIFO : First In First Out, 은행에서 번호표를 뽑고 기다리리는 것을 생각하면 편함)

 

-추가되는 곳은 Rear / 제거되는곳은 front

 

- 원소의 추가/제거 O(1)

- 제일 앞/뒤 원소확인 O(1)

- 앞/뒤가 아닌 원소의 확인 변경x

 

---

C++ STL - Queue

 

C++의 STL에서도 역시 Queue를 제공한다.

코테에서는 따로 구현할 필요 없이 <queue> 헤더파일을 포함시켜 사용하면 된다.

 

int main()
{
	queue<int> Q;

	Q.push(2); // 원소 삽입 2
	Q.push(3); // 원소 삽입 3

	if (!Q.empty()) //큐가 비어있는지 확인 후 제일 앞의 원소(2) 출력
		cout << Q.front() << endl;

	if (Q.size() != 0) //큐의 사이즈 확인 후 제일 뒤의 원소(3) 출력
		cout << Q.back() << endl;

	Q.pop(); //제일 앞의 원소 제거 (2 제거)
	
	cout << Q.front();

	return 0;
}

함수가 몇개 없기도하고 이름도 직관적이라 사용하기가 편하다.

정확한 내용은 아래 사이트에서 확인 하시면 된다.

https://cplusplus.com/reference/queue/queue/?kw=queue 

https://cplusplus.com/reference/queue/queue/?kw=queue

 

---

연습문제 풀어보기 - 10845번: 큐 (acmicpc.net)

10845번: 큐

스택과 똑같이 명령어를 입력받고 큐의 기능들을 실행하는 문제로, 어렵다기보다는 긴 코드를 작성해야하는 문제다.

 

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

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

    int n = 0;
    queue<int> myQueue;

    cin >> n;

    while (n--)
    {
        string s;
        cin >> s;

        if (s == "push")
        {
            int n;
            cin >> n;
            myQueue.push(n);
        }
        else if (s == "pop")
        {
            if (myQueue.empty()) cout << -1 << '\n';
            else
            {
                cout << myQueue.front() << '\n';
                myQueue.pop();
            }
        }
        else if (s == "size")
        {
            cout << myQueue.size()<< '\n';
        }
        else if (s == "empty")
        {
            if (myQueue.empty()) cout << 1 << '\n';
            else cout << 0 << '\n';
        }
        else if (s == "front")
        {
            if (myQueue.empty()) cout << -1 << '\n';
            else cout << myQueue.front() << '\n';
        }
        else
        {
            if (myQueue.empty()) cout << -1 << '\n';
            else cout << myQueue.back() << '\n';
        }

    }
    return 0;
}

 

어차피 다른 알고리즘을 사용하는 문제를 풀때 큐를 많이 사용하기때문에 큐의 응용문제들은 풀어보지 않았다.