[C++] STL 자료구조: Queue
queue는 stack과 다르게 시작 지점에서 pop이 가능하고 마지막 위치에 push가 가능한 자료구조이다.
queue는 들어온 순서대로 원소를 저장하고, 원소를 먼저 들어온 순서대로 꺼내야 할 때 주로 사용된다.
큐는 한 쪽에선 원소를 넣고 나머지 한 쪽에선 원소를 빼는 자료구조이다. 놀이공원에서 줄을 서서 기다리는 걸 생각하면 된다.
내부의 원소들은 먼저 삽입된 원소가 front쪽에 위치하며, 삭제는 항상 front쪽의 원소부터 가능하다.
이러한 특징을 FIFO(First In First Out)이라고 한다.
- push : back()쪽 위치에 원소를 삽입. O(1)
- pop : front()쪽 위치의 원소를 삭제. O(1) // 반환값은 void이며 front()가 아니다
- front : 가장 먼저 들어온 원소를 reference로 반환. O(1)
- back : 가장 마지막에 넣은 원소를 reference로 반환. O(1) (잘 사용하진 않음)
- size : queue의 크기를 size_t 자료형으로 반환.
- empty : queue가 비어있는지 여부를 bool 자료형으로 반환.
stack과 마찬가지로 queue도 clear하는 함수가 없다. queue가 빌때까지 계속 pop해줘야 한다.
백준>
10845번)
int main(){
fastio;
queue<int> Q;
int N,t;
cin>>N; //문자열 1개만 입력받으니 cin.ignore() 쓰지 않아도 됨
while(N--){
string s;
cin>>s;
if(s=="push"){
cin>>t; Q.push(t);
}
else if (s=="pop"){
cout<<(Q.empty()? -1:Q.front())<<'\n';
(Q.size()?Q.pop():void()); //size를 확인해서 0이 아닐때만 pop
}
else if (s=="size"){
cout<<Q.size()<<'\n';
}
else if (s=="empty"){
cout<<(Q.empty()? 1:0)<<'\n';
}
else if (s=="front"){
cout<<(Q.empty()? -1: Q.front())<<'\n';
}
else if (s=="back"){
cout<<(Q.empty()? -1: Q.back())<<'\n';
}
}
}
1158) 요세푸스
vector<int> Sol(int n, int k) {
vector<int> ret; queue<int> Q;
for (int i = 1; i <= n; i++) Q.push(i);
for (int i = 1; i <= n; i++) {
for (int i = 1; i < k; i++) {
Q.push(Q.front()); Q.pop();
}
ret.push_back(Q.front()); Q.pop();
}
return ret;
}
void Print(const vector<int>& v) {
cout << '<';
for (int i = 0; i < v.size(); i++) {
cout << v[i];
if (i != v.size() - 1) cout << ", ";
}
cout << '>' << '\n';
}
int main() {
fastio;
int n, k; cin >> n >> k;
auto v = Sol(n, k); Print(v);
}
1966) 프린터 큐