[바킹독의 실전 알고리즘] 0x06 큐 복습 -C++

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여,

필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다.

바킹독의 실전 알고리즘 0x06강 링크

 

강의내용 복습

큐의 정의와 성질

큐 : 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조(FIFO, First In First Out)

 

큐의 성질

1. 원소의 추가가 O(1)

2. 원소의 제거가 O(1)

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

4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

 

rear : 큐에서 원소가 추가되는 곳(뒤쪽)

front : 큐에서 원소가 제거되는 곳(앞쪽)

 

큐의 기능과 구현

배열과 연결리스트 어떤것으로도 구현은 가능하나, 배열이 구현하기 더 쉽다.

const int MX = 1000005;
int dat[MX]; //원소를 담을 큰 배열
int head = 0, tail = 0; //head는 가장 앞쪽, tail은 가장뒷쪽+1 인덱스를 가리킬 변수

dat[head]부터 dat[tail-1]번지 까지가 큐의 원소들이 들어있는 공간이다.

이때 큐의 크기는 tail - head이다.

 

스택과 달리, 큐는 배열로 구현하면 삭제가 발생할 때 마다 앞쪽에 잉여공간이 생긴다.

해결방법 : 원형큐(Circular Queue)로 만든다(관념적). 실제로는 head나 tail이 7인 상태에서 1이 더해지면 0번지로 가는 상태이다. 원소의 개수가 배열의 크기보다 커지지 않는 한 문제가 없다!

 

선형 큐 예시

#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;
    tail++;
}

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();  
}

 

STL queue

stl queue는 BFS와 Flood fill을 할때 많이 사용하게 될 것이다...

큐가 비어있을 때 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
}

 

연습문제 복습

강의 후반부 및 아래 링크로 들어가면 나오는 문제들 중 해당 강의에 맞는 연습문제들을 풀고

정답코드와 비교하며 얻은 내용들을 간단히 정리한 내용입니다.

연습문제 링크

 

 

*다풂