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

stack queue 비슷함

한쪽 긑에서 원소를 넣고 반대쪽 끝에서 뺼 수 있는 구조

먼저들어온게 먼저 나옴. 입국수속하듯 (FIFO)

 

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

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

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

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

 

큐에서 추가되는 곳을 rear, 제거되는 쪽을 front

 

그냥 배열로 front와 rear를 다루면 앞쪽이 누수됨.

circular queue를 구현하여 배열의 끝에 닿으면 처음 인덱스로 돌아오게 하여 누수로 인해 데이터 삽입 못하는 일 없앰..

 

구현

 

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

void push(int x) 
{
    if (tail == 10000005) return;
    dat[tail++] = x;
}

void pop()
{
    if (tail == 0) return;
    head++;
}

int front()
{
    if (tail == 0) return -1;
    return dat[head];
}

int back()
{
    if (tail == 0) return -1;
    return dat[tail - 1];
}

 

 

STL queue

 

보통 큐는 BFS랑 Flood Fill을 할 때 쓰게 된다. 단골이다 둘 다

 

#include <queue>

queue<int> q;
q.push(10); // 10
q.push(20); // 10, 20
q.push(30); // 10, 20, 30

q.size();
q.empty();
q.pop();
q.front();
q.back();

q.push(40);
q.pop();

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