[알고리즘/C++] 큐

수정 : 출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

'강좌/실전 알고리즘' 카테고리의 글 목록

- 큐 : 한 쪽에서는 원소가 들어갈 수만 있고, 반대편에서 나올 수만 있는 자료구조
  - First In, First Out(FIFO) 형태의 자료 구조

- 큐의 특징
  - 원소의 추가, 제거, 맨 앞/뒤 원소 확인 시 O(1)
  - 앞/뒤 외의 원소 확인은 원칙적으로 불가

- 큐의 구현
  - 배열을 이용한 구현

const int MAX = 100000;
int data[MAX];
int head = 0, tail = 0;
//head : 제일 앞에 있는 원소 / tail : 비어 있는 원소의 인덱스

// 데이터가 추가되면 tail이 1 증가
// 데이터가 제거되면 head가 1 증가
// 큐의 크기 = tail - head

void push(int x){
  data[tail++] = x;
}//데이터 추가

void pop(){
  head++;
}// 데이터 제거

int front(){
  return data[head];
}//맨 앞 데이터 반환

int back(){
  return data[tail-1];
}// 맨 뒤 데이터 제거

  - STL queue를 이용한 구현

#include <queue>
using namespace std;

int main(void){
  queue<int> q;
  
  q.push(10); // 데이터 추가
  q.pop(); // 데이터 제거
  cout << q.size(); // 큐 크기 반환
  q.front();
  q.back(); // 큐의 맨 앞 / 뒤 데이터 반환
  cout << q.empty(); // 큐가 비었는지 여부
}

  - 큐가 빈 상태로 pop / front / back을 호출 시 런타임 에러 주의