[(PS)DataStructure] 큐

바킹독님의 강의를 참고하였습니다.

https://blog.encrypted.gg/category/강좌/실전%20알고리즘

'강좌/실전 알고리즘' 카테고리의 글 목록

+ 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드.

+ 기록해두고 싶은 부분만 정리해 둠.

---

정의&성질

큐

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

스택에서는 먼저 들어간 원소가 나중에 나왔지만, 큐에선 먼저 들어간 원소가 먼저 나오게 된다.

 

상상해 보면 자명하다.

4번 성질의 이야기는 스택에서 다루었으니 생략.

---

STL queue

STL queue를 제공한다. 

큐는 보통 BFS와 Flood Fill을 할 때 쓰게 된다.

---

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

int main(void) {
    queue<int> q;
    q.push(element); // 큐에 데이터 추가
    q.pop(); // 큐의 front 데이터 삭제
    q.front() // 큐의 최상위 데이터(가장 먼저 들어온) 반환
    q.back() // 큐의 제일 마지막 데이터 반환
    q.size() // 큐의 현재 사이즈 반환
    q.empty() // 큐가 비어있는 지 확인
    swap(q1,q2) // 두 큐의 내용 바꿀 수 있음
}

STL queue는 이렇게 사용할 수 있다.