[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) 프린터 큐