큐(Queue)

🟩 FIFO (First In First Out)

 

🟩 BFS (너비우선탐색) 에서 활용

탐색 후보 중에서 항상 가장 오래된 것을 선택

 

🟩 <queue> 헤더 추가

 

🟩 주요 동작

enqueue : 삽입

dequeue : 추출

peek : 추출할 데이터의 값을 알 수 있음

 

🟩데이터 추가/삭제 방향이 반대

1 : 삽입 연산만 발생 (가장 위에 추가됨)

2 : 삭제 연산만 발생

 

🟩 중간에 있는 데이터에 접근 불가

필요한 데이터가 나올 때까지 dequeue

 

멤버 함수	기능
q.size()	q의 사이즈(물리적인 저장 용량이 아닌 원소의 개수)를 리턴
q.empty()	q의 사이즈가 0인지 아닌지를 확인
q.front()	q에 가장 먼저 들어간 원소를 리턴
q.back()	q에 가장 나중에 들어간 원소를 리턴
q.push(val)	q의 뒤에 val를 추가
q.pop()	q에 가장 먼저 들어간 원소를 삭제

 

 

queue<pair<int,int>> q;
 
q.push(make_pair(1,2));
 
int a = 2, b = 3;
pair<int,int> p = make_pair(a,b);
q.push(p);
 
cout << q.front().first << ' ' << q.front().second;        // 1 2
cout << q.back().first << ' ' << q.back().second;          // 2 3
 
//q가 비어있지 않은 동안
while(!q.empty())
{
    pair<int,int> n = q.front();
    q.pop();
 
    cout << n.first << ' ' << n.second << '\n';            // 1 2
                                                           // 2 3
}
 
cout << q.size();                                          // 0

q.push(make_pair(4,5));
q.push(make_pair(5,6));


queue<pair<int,int>> emt;
swap(q, emt);

cout << q.size();                                           // 0

 

자주 쓰이진 않지만, vector와 달리 queue는 clear() 멤버 함수가 없으므로, swap이라는 함수를 이용해 clear()하고자 하는 queue를 빈 queue와 swap해줌으로써 clear()와 같은 효과를 낼 수 있다. 이렇게 swap을 이용하는 것이 queue가 빌 때까지 원소를 pop()하는 것보다 빠르기 때문에 알아두는 것이 좋다.

 

 

🚀 원형큐

배열의 문제점을 해결하기 위해 고안됨

원형큐는 파이프의 입구와 출구 부분을 연결시킨 형태

연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 나머지 연산을 활용