0x06강 - 큐

목차

0x00 정의와 성질

0x01 기능과 구현

0x02 STL queue

0x03 연습문제 

 

---

0x00 정의와 성질

큐는 뒤에 원소를 넣고, 앞에서 원소를 빼는 자료구조다. 

큐 자료구조 방식은 넣은 순서대로 나오니깐, First In First Out 이라고 한다. FIFO

반대로 스택은 방금 넣은 것이 최상단에 있으니까 Last In First Out 이다. LIFO

 

스택과 똑같이 원소 추가/제거에 O(1) 시간이 걸린다. 

다른 점
큐는 뒤에서만 추가하고 앞에서만 제거한다.  => back에서 추가 front에서 제거 
스택은 top에서만 추가/제거한다. 

 

 

0x01 기능과 구현

배열을 이용해서 큐를 간단히 구현해보자. 

const int MX = 100005;
int dat[MX];
int head = 0, tail = 0;

데이터를 담을 배열을 선언한다.

데이터를 꺼낼 앞쪽 인덱스를 저장하는 head 와, 데이터를 넣을 뒤쪽 인덱스를 저장하는 tail을 선언한다. 

큐라는 자료구조와 STL queue에는 큐의 인덱스를 제공하지 않는다. 지금은 배열을 이용한 구현이기 때문에 인덱스를 이용한다. 

 

 

시작할 때는 tail 과 head가 모두 0 을 가리키고 있다. 

데이터를 넣고 빼고 하다보면, 자연스레 데이터가 뒤쪽 인덱스에 몰리게 된다. 

뒤에서 push 2번, 앞쪽에서 pop 1번

이를 해결하기위해 '원형 큐' 라는 개념을 쓴다. 

head나 tail이 마지막 인덱스(MX가 되면,) 7이 되면, 1이 더해질 때, 0번지를 쓰도록 하는 것이다. 

 

0x02 STLqueue

큐에서는 빼내는 앞쪽의 원소를 확인하는 front() 와 넣는 뒤쪽의 원소를 확인하는 back()이 있다. 

큐 레퍼런스 

// Authored by : std-freejia
#include <bits/stdc++.h>
using namespace std;

int main(void) {

  queue<int> qu;

  qu.push(10);  // 10
  qu.push(20);  // 10 20
  qu.push(30);  // (앞) 10 20 30 (뒤)

  cout << qu.size() << '\n';

  if(qu.empty()) cout << "Q is empty\n";
  else cout << "Q is not empty\n";

  qu.pop(); // 20 30
  cout << qu.front() << '\n';  // 20
  cout << qu.back() << '\n';   // 30
  qu.push(40); // 20 30 40
  qu.pop();       // 30 40

  return 0;
}

실행 결과 

3
Q is not empty
20
30

 

0x03 연습문제 

큐 문제집

문제번호	내 코드
10845번 큐	내 코드
18258번 큐2	내 코드
2164번 카드2	내 코드

 

---

다음 시간에는 deque 덱을 배운다.

공부 자료 출처 : 바킹독 알고리즘 큐