바킹독님의 실전알고리즘배우기 6강듣고 요약

바킹독의 실전 알고리즘 6강 링크

image
image

큐의 성질

image

큐의 구현

image
큐는 배열로 구현하면 점점 원소들이 뒤로 밀리기 때문에 큐를 구현할 땐 위 그림처럼 tail과 head가 연결되는 원형 큐로 구현하는게 좋다.

하지만 코딩테스트에서는 입출력의 수가 정해져있기 때문에 충분히 배열의 크기를 크게 만들기만 하면 된다.
따라서 밑의 큐 구현 코드는 선형 큐이다.

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

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

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

void pop(){
  head++;
}

int front(){
  return dat[head];
}

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

void test(){
  push(10); push(20); push(30);
  cout << front() << '\n'; // 10
  cout << back() << '\n'; // 30
  pop(); pop();
  push(15); push(25);
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 25
}

int main(void) {
  test();  
}

큐도 구현이 쉽지만 역시 STL의 queue를 이용하는 것이 좋다.

STL queue

image
STL queue의 기본적인 함수로는 push(), pop(), front(), back() size(), empty()가 있다.
queue가 비어있는데 pop()이나 front(), back()을 호출하면 runtime error가 발생한다.

연습문제

BOJ 10845번