Queue, 큐 , 자료구조 [CPP]

 

 

자료구조의 큐에 대해서 알아보자

 

 

First In First Out의 구조를 가지고 있으며

방향성이 있는 자료구조이다.

삽입과 삭제 연산이 일어나는 곳이 다르다는 이야기다.

-> 이 개념이 가장 중요하다. 이러한 일을 처리할 때 쓰는 것이다.

또한 삽입,삭제 연산에 있어서는 상수의 시간복잡도를 가진다.

 

** 주로 순차적으로 진행되어야 하는 일을 스케줄링할 때 사용된다.

 

---

 

주로 우리의 일상적으로 쓰는 곳에 있다.

줄을 서서 기다리는 모든 것들이 큐와 같다.

 

 

---

 

** 큐를 CPP에서 사용하기 위해서는 헤더를 사용해서 포함시켜야 한다.

 

큐를 선언할 때 원소가 될 자료형을 선언하며 크기는 선언하지 않았다.

 

하지만 enqueue와 dequeue를 사용하는 대신 

 

push() 와 pop()를 사용하며

-> push는 back에 삽입

-> pop()은 front에서 삭제

front() 와 back() 으로 값을 삭제하지 않고 반환받을 수 있으며

size() 로 큐에 담겨진 크기를, 알 수 있고

empty()로 큐가 비어있는지 알 수 있다.

 

---

 

예를 들어

www.acmicpc.net/problem/2164

 

 

#include <iostream>
#include <queue>


int main(){
    //사용할 변수
    int num;
    std::queue<int> q;
    
    //입력받음
    std::cin >> num;
    
    //큐에 집어넣음 i = 1부터 시작임
    for(int i =1; i<= num; i++){
        q.push(i);
    }
    
    //큐에서 계산
    while(q.size() != 1){
        q.pop();
        q.push(q.front());
        q.pop();
    }
    
    //결과 출력
    std::cout << q.front();
    
    
    
    
}

 

여기서 중요한 것은 문제가 큐를 이용하느냐? 를 아는 것이다.

큐를 이용하는 것이다라고 알고 푸는 것은 의미가 없다.

 

어디에서 큐를 이용하는 것을 찾을 수 있을까??

 

버리는 행위 -> 삭제

밑으로 옮기는 행위 -> 삭제한 것을 삽입하는 행위

 

저런 정렬느낌의 문제에서는 삽입과 삭제가 일어나는 조건, 상황이 중요하다.

삭제는 카드의 맨 위

삽입은 카드의 맨 아래에서 일어난다.

삽입과 삭제의 일어나는 장소가 다르다.

 

이를 파악할 수 있다면 나머지는 수학문제다.

 

다른 문제를 보자

 

---

www.acmicpc.net/problem/1158

 

문제를 처음 딱 보면 삽입은 일어나지 않는 것으로 보이고 삭제는 일어나는 것처럼 보인다.

하지만 보면 방향성이 보인다.

**삭제는 K번째 사람을 제거한다에서 알 수 있다.

 

(7,3) 이라고 하면

1234567123456712345671234567을 충분히 해놓고 

위와 같은 배열에서 3의 space를 두고 7번 뽑으면 될 것 같다.

하지만 메모리가 필요 이상으로 필요하기 때문에

큐를 이용해서 7개로도 위와 같이 계산이 되게 만들 수 있다.

원이라고 써놓았기 때문에 원형 큐를 생각하면 된다.

 

#include<iostream>
#include<queue>
#include<vector>

int main(){
    int N,K;
    std::queue<int> q;
    std::vector<int> answer;
    
    
    std::cin >> N >> K;
    
    //생성
    for(int i = 1; i<=N; i++){
        q.push(i);
    }
    
    //순서대로 삭제하고 살아남은 사람은 순서대로 다시 큐에 들어감.
    while(!q.empty()){
        for(int j = 1; j< K; j++){
            q.push(q.front());
            q.pop();
        }
        //정답에 넣어줌
        answer.push_back(q.front());
        q.pop();
        
    }
    
    //츨력
    std::cout << '<' << answer[0];
    for(int i = 1; i < answer.size(); i++){
        std::cout << ", " << answer[i];
    }
    std::cout<< ">";
    
    
}

 

 

---

 

다시 생각해보자.

순서가 있는 문제는

어떤 자료구조로 구성해야하는지 생각해봐야한다.

 

즉, 문제를 보았을 때 삽입, 수정, 삭제가 일어나는 곳이 어디인가?

일정한 방향성을 가지고 일어나는가?

를 보면 조금씩 감이 잡힐 것이다.

 

물론 나도 아직 멀었다.

하지만 이런 식으로 생각하니까 조금씩 감이 잡히더라 이얘기다.

 

 

 

---

참고링크

github.com/VSFe/Algorithm_Study