[ 자료구조 ] 큐 Queue 정리 및 STL 사용법

 

# 큐를 이용한 문제를 풀고 싶다면, 블로그에서 큐를 검색하면 관련 문제 풀이 글을 보실 수 있습니다. 그 글에 문제 링크도 있으니 한 번 풀어보시는 걸 추천합니다. 

큐란?

큐란, FIFO의 구조를 가진 자료구조를 의미한다. 여기서 FIFO는 First In First Out이다. 처음 입력된 요소가 가장 먼저 출력된다. 

 

위의 그림을 참조하면 이해하기 쉬울 것이다.

1. 3을 입력을 하게 되면 맨 앞에 위치합니다
2. 이어 4를 입력하면 3 뒤에 위치하게 됩니다
3. 위의 과정을 반복합니다
4. Pop을 하면 가장 앞에 있는 요소인 3을 출력하고 삭제합니다

이러한 과정으로 삽입/삭제가 이루어지는 것을 FIFO라고합니다. FIFO의 대표적 자료구조는 큐입니다

 

큐 활용 

1. 너비 우선 탐색 구현 : 연결된 모든 노드를 큐에 입력을 하고 순회를 할 때, pop하면서 순회를 합니다.
2. 캐시구현
3. 티켓 카운터와 같은 선입선출이 필요한 대기열
4. 콜센터 고객 대기시간
5. 프린터의 출력 처리
6. 윈도 시스템의 메시지 처리기
7. 프로세스 관리 

 

큐 구현 _ 배열

#include <iostream>
using namespace std;
int main() {

	int list[1000] = { 0 };
	// 배열 선언시,초기화를 필수적입니다.
	
	int front_point = 0;
	int end_point = -1;

	for (int i = 0;i < 10;i++) {
		list[++end_point] = i;
	}
	// list 상태 : 0 1 2 3 4 5 6 7 8 9

	list[front_point--]=0;
	// list 상태 : 1 2 3 4 5 6 7 8 9

	list[front_point--] = 0;
	// list 상태 : 2 3 4 5 6 7 8 9



	return 0;
}

이렇게 배열로 큐를 구현하고 큐의 맨앞 요소를 가리키는 변수 하나하고 맨끝 요소를 가리키는 변수하나 총 2개의 변수로 인덱스를 관리한다. 

큐에 요소를 입력할 경우, end_point를 증감시키고 그 위치에 추가한다. 삭제할 경우, front_point 위치의 값을 0으로 만드고 front_point를 감소시켜준다.

여기서 치명적인 단점이 나온다. 바로 공간의 낭비이다. 자료를 입력하고 pop을 할수록 나중에 입력할 수 있는 여유공간이 부족해진다. 

단순히 모든 데이터를 앞으로 이동시키면 되지 않냐라는 의문을 가질 수 있다. 이는 적은 데이터일 때는 가능하지만, 데이터량이 만단위가 되면 이동시키는데 너무 많은 시간이 걸리기에 부적합하다. 그렇기에 배열로 큐를 사용할 때는 주의가 필요하다.

 

큐 구현 _ STL

#include <iostream>
#include <queue>
using namespace std;
int main() {

	queue<int> q;
	for (int i = 0;i < 10;i++) {
		q.push(i);
	}
	// q의 상태 : 0 1 2 3 4 5 6 7 8 9


	cout<< q.front();
	//q.front()의 요소 : 0

	q.pop();
	// q의 상태 : 1 2 3 4 5 6 7 8 9

	q.pop();
	// q의 상태 : 2 3 4 5 6 7 8 9

	return 0;
}

큐 STL을 사용하기 위해서는 필수적으로 #include <queue> 을 적어주어야한다.

queue<int> q; int형의 큐인 q를 선언한다.

q.push(1); 큐 q에 1을 추가한다. 

q. front(); 큐 q의 가장 앞 요소를 의미한다. 

q.pop(); 큐 q의 가장 앞 요소를 삭제한다. 

q.empty(); 큐 q가 비어있는지 확인한다. 비어있으면 true를 의미하고 안에 값이 있다면 false를 의미하다. 이는 if문에 유용하게 사용된다. ex) if(q.empty()) { (1) } 라고 코딩하면 q 안에 값이 없을 때, (1)의 코드가 실행된다.

q.size(); 큐 q의 크기를 리턴한다. 만약 s에 값이 4개가 들어가 있다면, s.size()는 4를 의미한다. 이는 for문에서 유용하게 사용된다. ex) for(int i=0;i<s.size();i++){ q.pop(); } 처럼 사용하면 for이 q사이즈만큼 돌면서 모든값을 pop할 수 있다.