[C++] queue 클래스 정리
🦥 queue?
▶ FIFO (First In First Out) 구조의 Container Adapter
1) First In First Out (선입 선출)
queue는 한 쪽으로 원소를 넣고 다른 쪽으로 빼는 구조이다. 이때, 원소를 넣는 쪽을 ‘front’, 빼는 쪽은 ‘back’이라고 한다.
‘queue’를 사전에 찾아보면 ‘줄을 서서 기다리다’라는 뜻이 나온다. 우리가 줄을 서서 기다릴 때 먼저 줄을 선 사람이 먼저 들어가는 것처럼, 가장 먼저(First) 넣은(In) 원소가 가장 먼저(First) 나오는(Out) 구조를 queue이라고 한다.
2) Container Adapter
template<
class T,
class Container = std::deque<T>
> class queue;
queue는 container가 아니라 container adapter이다.
즉, 기존의 container(list, deque)를 기반으로 구현된 구조로, 해당 container가 가지고 있는 일부 member function을 활용할 수 있다. default container는 deque이기 때문에 따로 명시하지 않고 queue<int> q로 선언하게 되면, deque를 기반으로 한 queue가 생성된다.
stack과 달리 vector를 컨테이너로 쓸 수 없는 이유는, vector는 pop_front()가 없고 한 방향에서만 push와 pop을 하는 구조라서, front에서 pop하고 back에서 push하는 queue와 맞지 않기 때문이다.
✅ 이 포스트는 C++ STL에서의 queue에 대한 글입니다. queue 자료구조의 특징, 장/단점, 시간 복잡도에 대해서 더 알아보려면 ▶ [자료구조] 스택(Stack), 큐(Queue), 덱(Deque)
🦥 queue의 생성자와 초기화
queue 헤더 추가
#include <queue>
1) 비어있는 queue 생성
queue<int> q1;
2) {1, 2, 3, 4, 5}로 초기화 된 queue 생성
// q2.front()하면 1이 나오고 q2.back()하면 5가 나온다
queue<int> q2({ 1, 2, 3, 4, 5 });
3) container(deque, list)를 복사하여 stack을 생성
deque<int> dq1;
dq1.push_back(1);
dq1.push_back(2);
dq1.push_back(5);
queue<int> q1(dq1);
4) queue를 만드는 container를 명시하여 생성
First parameter : Type of the stored elements
Second parameter : Type of the underlying container to use to store the elements
// list를 container로 하는 queue 생성
queue<int, list<int>> q3;
// deque를 container로 하는 queue 생성 (queue<int> q4와 동일)
queue<char, deque<char>> q4;
🦥 queue의 함수들
🌴 Iterator
사용 안함. queue의 목적이 iterator를 필요로 하지 않기 때문.
🌴 Fuction
q.empty(): queue가 비어있는지 확인 / 시간 복잡도 : O(1)q.size(): queue의 원소 수를 반환 / 시간 복잡도 : O(1)q.front(): queue의 맨 앞의 원소 리턴 / 시간 복잡도 : O(1)q.back(): queue의 맨 뒤의 원소 리턴 / 시간 복잡도 : O(1)q.push(n): queue의 맨 뒤에 원소 추가 / 시간 복잡도 : O(1)q.pop(): queue의 맨 앞의 원소 삭제 / 시간 복잡도 : O(1)
실습 코드
#include <iostream>
#include <queue>
using namespace std;
void showAll(queue <int> q)
{
while (!q.empty())
{
cout << q.front() << ' ';
q.pop();
}
}
int main()
{
queue <int> q;
q.push(10);
q.push(20);
q.push(30);
cout << "Show all queue elements : ";
showAll(q);
cout << "\nq.size() : " << q.size();
cout << "\nq.front() : " << q.front();
cout << "\nq.back() : " << q.back();
cout << "\nq.pop()\n";
q.pop();
cout << "Show all queue elements : ";
showAll(q);
cout << "\nq.push()\n";
q.push(50);
cout << "Show all queue elements : ";
showAll(q);
return 0;
}
[실행 결과]
Show all queue elements : 10 20 30
q.size() : 3
q.front() : 10
q.back() : 30
q.pop()
Show all queue elements : 20 30
q.push()
Show all queue elements : 20 30 50
Reference
Leave a comment