[C++] STL queue

개요

queue가 가지는 특징과 STL queue의 사용법을 정리해봤다.

Queue

queue는 뒤로 원소를 삽입하고 앞에서 원소를 꺼내는 "FIFO" 자료구조이다.

특징으로는

• 원소 삽입 O(1)
• 원소 제거 O(1)
• 원소 상단/하단 확인 O(1)
• 임의의 원소 접근 불가

구현

배열로 간단히 구현 가능하다.

앞과 뒤의 index를 확인해야하므로 head, tail이 필요하다.

int q[100]
int head = 0;
int tail = 0;

head는 맨 앞의 원소를 가르키고 tail의 경우 맨 뒤의 원소의 index + 1의 값을 가지고 있다.

그 이유는  queue가 비었는지 확인을 head == queue로 쉽게 구할 수 있기 때문이다.

기능 구현

• push : q[tail++] = data
• pop : head++;
• front : q[head]
• back : q[tail-1]
• size : head - tail
• empty : head == tail

 

원형 queue로 구현하게 된다면

• 비었는지 확인 : head == tail
• 꽉찼는지 확인 : head == tail + 1

STL queue

queue가 비어있을 때 front(), back(), pop()을 실행한다면 런타임 에러가 발생하므로 주의해야한다.

#include <bits/stdc++.h>
using namespace std;

int main(){
	queue<int> Q;
    Q.push(10);
    Q.push(20);
    Q.push(30);
    
    cout << Q.size() << "\n";
    
    if(Q.empty()) cout << "queue is empty\n"
    
    Q.pop();
    
    cout << Q.front() << '\n';
    cout << Q.back() << '\n';
}