[알고 공부] 0x06강 - 큐

출처 : 바킹독 https://blog.encrypted.gg/934

 

 

큐

FIFO(First in First Out)

rear : 추가되는 곳 

front : 뒤쪽, 제거되는 쪽 

4. 큐라는 자료구조에서는 인덱스를 가지고 원소에 접근하는 기능이 없지만, 배열을 가지고 직접 만들 땐 해당 기능이 가능하도록 구현 가능. . 단, STL queue에는 인덱스로 내부 원소를 접근하는 기능X

 

원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개가 필요 

head :가장 앞에 있는 원소의 인덱스

tail : 가장 뒤에 있는 원소의 인덱스 + 1

tail - head : 큐의 크기

 

원형 큐(Circular Queue)

선형 배열로 구현시 삭제마다 쓸모 없는 공간이 계속 생성되어 앞 공간은 많은데 새 원소를 추가할 수 없는 상황이 생길 수 있음

=> 원형 큐는 head와 tail이 다시 앞쪽으로 돌아오기 때문에 원소의 갯수가 배열의 크기보다 커지지 않는 한 문제 X

 

코테에서는 push의 최대 횟수가 정해져 있어서 배열 크기를  push의 최대 횟수보다 크게하면 됨

(굳이 원형 큐 만들 필요 X)

 

직접 구현

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

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];
}

 

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
}

보통 큐는 BFS랑 Flood Fill할 때 사용

큐가 비어있는데 front나 back이나 pop을 호출하면 런타임 에러 발생