바킹독 알고리즘 0x06강 큐 요약본

1. 큐는 한쪽 끝에서 원소를 넣고, 다른 쪽 끝에서 원소를 제거할 수 있는 자료구조이다. 

2. 스택과 마찬가지로, 맨 앞과 맨 뒤가 아닌 원소의 확인/변경이 원칙적으로 불가하다.

3. 큐가 추가되는 곳을 rear 라 하고 큐가 제거되는 곳을 front 라 한다.

4. 배열로 큐를 구현한다고 했을 때, 큐를 구현하려면 1, 원소를 담을 충분히 큰 배열 2, 배열의 원소 중 rear 원소를 가리키는 head 변수, front 원소 + 1의 빈 공간을 가리키는 tail 변수 이렇게 세 가지가 필요하다.

처음에는 head 와 tail 이 같은 곳을 가리킨다.

5. 큐의 크기는 tail - head 로 쉽게 계산 가능하다.

6. 스택과는 달리 큐의 경우 삭제가 발생할 시, head 가 오른쪽으로 밀려나기 때문에 메모리 공간 낭비가 있다. 이를 해결하기 위해 큐를 원형으로 만들면 된다. head 나 tail 이 맨 마지막 요소에 온 뒤에 1이 더해지면 다시 1로 돌아오게 설계하면 된다. 근데 코테에서는 그냥 큐의 원소를 담는 배열의 크기를 충분히 크게 잡으면 되므로 원형 큐를 사용할 일은 거의 없다.

7. 큐는 BFS 와 flood fill 을 할 때 쓰게 된다.

8. STL 로 구현한 큐

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  queue<int> Q;
  Q.push(10); // 10
  Q.push(20); // 10 20
  Q.push(30); // 10 20 30
  cout << Q.size() << '\n'; // 3
  if(Q.empty()) cout << "Q is empty\n";
  else cout << "Q is not empty\n"; // Q is not empty
  Q.pop(); // 20 30
  cout << Q.front() << '\n'; // 20
  cout << Q.back() << '\n'; // 30
  Q.push(40); // 20 30 40
  Q.pop(); // 30 40
  cout << Q.front() << '\n'; // 30
}

9. 큐도 스택과 마찬가지로 빈 큐에서 front rear pop 을 호출하면 런타임 에러가 발생한다.