앞서 포스팅에서 스택을 정리한 방식과 같게 큐를 정리한다.
자료구조 큐의 특성에 대해서 소개하고, 코드로 사용하는 방법을 소개한 후에 이를 활용한 간단한 문제풀이까지 진행해본다.
1. What is Queue?
큐(Queue)는 스택과 다르게 먼저 들어온 것이 나가는 "선입선출"로,
FIFO(First in First Out)의 구조를 가지고 있다.
(스택은 세로로 아래가 닫혀있는 구조를 생각하면 편하고, 큐는 양쪽이 열려있는 가로구조를 생각하면 활용하기 좋다고 생각한다. 아래 그림을 머릿속에 담아두도록 하자 . . ! )
일반적으로 카페에서 먼저 와서 주문한 손님이 음료를 먼저 받아서 나가는 구조를 생각해도 좋다.
스택과는 다르게 삭제와 삽입이 다른 곳에서 이루어지는 FIFO구조의 특성상 스택에서의 top역할을 할만한 곳이 두 군데 있다.
삭제 연산이 진행되는 곳을 front, 삽입이 이루어지는 곳을 rear라고 부르며 rear에서의 삽입 연산을 Enqueue(push), front에서의 삭제 연산을 Dequeue(pop)이라고 부른다.
2. How to use Queue?
1) Queue 선언
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<int> que;
queue<char> letters;
queue<string> words;
return 0;
}스택 포스팅에서와 Pair를 맞추기 위해 의도적으로 코드를 유사하게 짰다.
queue include 해주고 queue<자료형> (자료구조 이름)의 형태로 선언한다.
2) Queue 데이터 처리 및 접근
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<int> que;
//Queue에 값 추가
que.push(1);
que.push(2);
que.push(3);
//Queue의 front와 rear값 출력해보기!
cout << "front : " << que.front() << "\n";
cout << "rear : " << que.back() << "\n";
//Queue의 값 제거
que.pop();
return 0;
}
정리한 내용을 토대로 보면 마지막에 pop을 해주기 전까지는 위의 그림과 같은 상황으로 큐에 데이터들이 담겨있을 것이고, 출력결과는 다음과 같다.
PS) rear에 접근하기 위해서는 back이라는 내장함수로 접근해야한다.
(사실 스택에서 top 사용하듯이, 큐에서도 front정도 인지하고 있으면 된다. 결국에 뒤에 bfs에서 큐를 지겹도록 사용할텐데 front가 주인공이라...!)
3) 기타 함수(size/empty)
크기를 출력해주는 내장함수 size와 비어있는지 확인하는 empty에 대해서는 Stack에서와 동일하므로 자세한 설명은 생략하도록 한다.
코드와 함께 정리해보자.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<int> que;
//Queue에 값 추가
que.push(1);
que.push(2);
que.push(3);
//Queue의 front와 rear값 출력해보기!
cout << "front : " << que.front() << "\n";
cout << "rear : " << que.back() << "\n";
//Queue의 Size 출력
cout << "Queue의 크기: " << que.size() << "\n";
if (que.empty())
cout << "Queue is Empty";
else
cout << "Queue is not Empty";
cout << "\n";
//빌 때까지 반복문 이용해서 pop해줌.
while (!que.empty())
{
que.pop();
}
if (que.empty())
cout << "Queue is Empty";
else
cout << "Queue is not Empty";
return 0;
}빌 때까지 반복문 이용해서 pop해주는 방식은 추후에 BFS(너비 우선 탐색)활용 시에 지겹도록 사용하니 눈에 익혀두도록 하자!
실행 결과는 다음과 같다.
3. Problem Solving (feat. BOJ)
마지막으로 큐 자료구조의 기본을 확인할 수 있는 필수 문항 하나를 풀이해보자.
//BOJ 18258번
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
string order;
int temp;
queue<int> que;
while (n--)
{
cin >> order;
if (order == "push")
{
cin >> temp;
que.push(temp);
}
else if (order == "front")
{
if (que.size() == 0)
cout << -1 << "\n";
else
cout << que.front() << "\n";
}
else if (order == "back")
{
if (que.size() == 0)
cout << -1 << "\n";
else
cout << que.back() << "\n";
}
else if (order == "size")
cout << que.size() << "\n";
else if (order == "empty")
{
if (que.empty())
cout << 1 << "\n";
else
cout << 0 << "\n";
}
else if (order == "pop")
{
if (que.empty())
cout << -1 << "\n";
else
{
cout << que.front() << "\n";
que.pop();
}
}
}
return 0;
}스택에서의 기본 문제와 거의 유사하다.
마찬가지로 비어있을 때의 예외에 대해서만 신경써서 처리해주자..!
PS) 별 것 아닌 세 줄의 중요성에 대하여...
걸린 시간을 비교해보면 물론 ms단위이므로 크지 않은 차이라고 생각할 수도 있으나, Time Error가 자주 발생하는 것을 감안하면 꽤나 중요할 수 있다.
그렇다면 작성한 1번 코드와 2번 코드는 무엇이 다를까?
별 것도 아닌 다음 3줄의 입력 여부 차이이다.
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
작성 시에 상당한 시간 Save를 할 수 있기에 쓰는 습관을 들인 편인데
이 세 줄 작성이 왜 실행속도를 높이는 지 관련해서는 참고할만한 Reference를 남기도록 한다.
