[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 큐(Queue)
- STL queue
- Q&A
- 마치며
1. 큐(Queue)
- 큐(Queue)
: 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺼 수 있는 자료구조
스택은 구조적으로 제일 먼저 들어간 원소가 제일 나중에 나오게 됨.
FILO(First in Last out) 자료구조.
큐는 먼저 들어간 원소가 제일 먼저 나오게 됨.
FIFO(First in First out) 자료구조.
1) 큐의 성질
(1) 원소의 추가 / 제거 O(1)
스택에서는 원소가 추가되고 제거되는 곳을 top이라고 함. 그리고 원소가 위 아래로 배치된 것으로 생각함.
큐에서는 추가되는 곳을 rear(뒤쪽), 제거되는 곳을 front(앞쪽)이라고 함.
(2) 제일 앞 / 뒤의 원소 확인 O(1)
(3) 제일 앞 / 뒤가 아닌, 나머지 원소들의 확인 / 변경이 원칙적으로 불가능
2) 스택의 구현
const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;dat배열에는 스택 원소들의 값이 들어가고, head는 제일 앞의 원소를 가리키고, tail은 제일 뒤의 원소 + 1을 가리키고 있음.
그리고 dat[head]부터 dat[tail - 1]까지 큐의 원소들이 있는 자리임. 그리고 큐의 크기는 tail - head로 계산 가능.
push를 하게되면 tail이 증가, pop을 하면 head가 증가.
따라서 dat배열에서 큐의 원소들이 있는 장소는 오른쪽으로 점점 밀림.
그러면 pop을 여러 번 진행하면, 앞쪽에 쓸모없는 공간이 계속 생기게 됨.
이를 해결하기 위해서는, 큐의 언소가 들어갈 배열을 원형으로 만드는 것.
실제로 구현할 때는 head나 tail이 다시 0번지로 돌아오게끔 구현.
이러한 원형 배열로 만든 큐를 '원형 큐(Circular Queue)'라고 함.
그래서 실무에서 STL말고 큐를 직접 구현을 할 때는 원형 큐를 구현하는 것이 좋음.
const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;
void push(int x){
dat[tail++] = x;
}
void pop(){
head++;
}
int front(){
return dat[head];
}
int back(){
return dat[tail - 1];
}2. STL queue
queue는 보통 BFS나 Flodd Fill을 할 때 쓰게 됨.
둘 다 코테 단골 문제여서 queue를 쓸 일이 아주 많을 것.
1) 생성자
1. queue<int> Q;1번은 비어있는 큐를 생성합니다.
(스택과 마찬가지로 queue는 내부적으로 queue 연산을 지원하는 deque, list 등을 이용해 구현되며, default값은 deque입니다.)
2) 멤버 함수
queue<int> Q;
// Q = [ 1(front), 2, 3, 4, 5(back) ]
for(int i = 1; i <= 5; i++) Q.push(i);
while(!Q.empty()){
cout << Q.size() << ' ' << Q.front() << '\n';
Q.pop();
}(1) push / pop
back()쪽 위치에 원소를 삽입. O(1)
front()쪽 위치에 원소를 삭제. O(1)
push는 emplace로 대체 가능.
pop의 반환값은 void이며 front()가 아님.
(2) front / back
가장 먼저 들어온 원소를 reference로 반환. O(1)
가장 마지막에 들어온 원소를 reference로 반환. O(1) (잘 사용하지 않음)
(3) size / empty()
queue의 크기를 size_t 자료형으로 반환.
queue가 비어있는지 여부를 bool 자료형으로 반환.
(4) 참고
std::queue에는 clear라는 멤버 함수가 없음.
따라서 해당 동작을 하고자 하면
while(Q.size()){ Q.pop() }으로 처리해야 함.
빈 Queue에서 pop, front, back을 호출하는 것은 'UB(Undefined Behavior)'이며 런타임 에러를 발생시킴.
일반적으로 큐의 원소에 접근할 때는 front()만을 이용하며, back()이 필요한 경우는 드뭄.
또한 deque와 달리 []연산자, iterator가 없으므로 front(), back() 이외의 원소에는 접근할 수 없음.
3. Q&A
-
4. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
