[바킹독의 실전 알고리즘] 0x06강 - 큐

1. 정의와 성질

 

정의

 

한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조. 먼저 들어간 원소가 먼저 나옴!(FIFO)

 

성질

 

1) 원소의 추가 시간복잡도는 O(1)

2) 원소의 제거 시간복잡도는 O(1)

3) 제일 앞/뒤의 원소 확인이 O(1)

4) 제일 앞/뒤가 아닌 나머지 원소들의 확인 및 변경은 원칙적으로 불가능함!

 

2. 기능과 구현

직접 구현

큐도 스택처럼 배열 혹은 연결 리스트 둘 중 어느 것을 이용해서 구현 하는데 문제가 없지만 배열이 훨씬 쉽기 때문에 배열로 가보는 걸로! 배열에서 제일 위에 있는 원소를 가리키는 pos 변수가 1개 있었던 스택과 다르게, 큐에서는 앞쪽을 가리키는 head와 맨 뒷쪽을 가리키는 tail이 존재해 총 2개의 변수가 활용됨.

 

배열로 구현하는 과정에서 원소들을 삭제하는 연산의 코드를 보자. pop() 연산을 할 때 head 변수 위치만 바꿔주는 것을 알 수 있음. 생각하보면 결국 앞의 메모리는 다 낭비를 하는 것임! 따라서 이보다 더 좋은 방법은 원형큐를 활용할 수 있음. 원형큐에서는 head나 tail이 배열의 마지막 인덱스에 도착을 한 상황에서 다음으로 이동 시 다시 0번지로 이동을 하는 방식의 큐임.하지만 코테에서는 push의 횟수가 정해져 있기 때문에, 배열의 크기를 push 횟수보다 크게 만드는 식으로 하는 게 편리함.

 

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

void test(){
  push(10); push(20); push(30);
  cout << front() << '\n'; // 10
  cout << back() << '\n'; // 30
  pop(); pop();
  push(15); push(25);
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 25
}

int main(void) {
  test();  
}

 

3. STL Queue

보통 큐는 BFS(너비 우선 탐색)나 Flood Fill(오옹? 이건 첨 들어본다..)을 할 때 많이 쓴다고 함. 둘 다 코테 단골 문제여서 STL queue는 아아아아아주 많이 쓰인다고 하니 자연스래 외워질 정도라고..

 

아래는 STL queue를 사용한 예시임. 이때 큐가 비어있는데 front, back, pop()을 호출하면 런타임에러 발생하니 주의!

#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
}

 

📌 STL queue 참고자료https://cplusplus.com/reference/queue/queue/