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

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

image
image

덱의 성질

image
덱은 double-ended queue로, 큐인데 양끝에서 삽입과 삭제가 가능한 자료구조이다.
양 끝의 원소 이외의 원소들은 원칙적으로 확인이 불가능하지만, STL deque에서는 가능하다.

덱의 구현

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

const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;

void push_front(int x){
  dat[--head] = x;
}

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

void pop_front(){
  head++;
}

void pop_back(){
  tail--;
}

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

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

void test(){
  push_back(30); // 30
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 30
  push_front(25); // 25 30
  push_back(12); // 25 30 12
  cout << back() << '\n'; // 12
  push_back(62); // 25 30 12 62
  pop_front(); // 30 12 62
  cout << front() << '\n'; // 30
  pop_front(); // 12 62
  cout << back() << '\n'; // 62
}

int main(void){
  test();
}

덱은 양쪽으로 확장이 가능하기 때문에 직접 구현할 땐 초기 시작점인 head와 tail을 MX로 두고, 배열의 크기를 2 * MX + 1로 잡는다.

STL deque

image
STL deque는 push_front(), push_back(), pop_front(), pop_back(), front(), back() 등 deque의 기본적인 함수 뿐만 아니라
insert(), erase(), at(), , iterater(begin(), end())까지 vector에서 지원하는 연산을 다 지원한다.
그렇다고 vector보다 deque가 더 좋은 것은 아니고, 처음, 중간에서 삽입과 삭제가 빈번할 땐 deque를 사용, 끝에서 추가 삭제가 빈번할 땐 vector가 좋다.
또한 둘은 메모리 배치가 다르다. vector는 원소들이 메모리 상에 연속적으로 배치되어있고, deque는 분산되어있다

출처
출처

연습문제

BOJ 10866번