[바킹독] 6. 큐

https://www.youtube.com/watch?v=D_fwSy5tRAY

https://blog.encrypted.gg/934

[실전 알고리즘] 0x06강 - 큐

 

1. 정의와 성질
2. 기능과 구현
3. STL queue
4. 연습 문제 

 

1. 정의

큐 : 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조

스택과 달리, 먼저 들어간 원소가 먼저 나오게 됨 

FIFO(First in First Out)

 

 

2. 성질

1) 원소 추가 : O(1) <- 뒤쪽, rear

2) 원소 제거 : O(1) <- 앞쪽, front

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

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

 

 

3. 구현

1) 큐 - 배열

 

2) 원형 큐

배열로 구현하면 삭제가 발생할 때 마다 앞쪽에 쓸모없는 공간이 계속 생기는 문제를 해결하는 방법

-> 큐의 원소가 들어갈 배열을 원형으로 만듦 (관념적으로는 배열이 원형인거고, 실제 구현을 할 땐 head나 tail이 7인 상태에서 1이 더해질 때 0번지로 다시 오도록)

 

3) push 함수

 

4) pop 함수

 

5) front/back 함수

front : 큐에서 제일 앞에 위치한 원소를 반환하는 함수

back : 큐에서 제일 뒤에 위치한 원소를 반환하는 함수 

 

4. STL queue

https://cplusplus.com/reference/queue/queue/

https://cplusplus.com/reference/queue/queue/

 

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
}