[알고리즘 공부] 실전 알고리즘 7강-덱

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

---

정의

덱은 양쪽 끝에서 삽입/삭제가 가능한 자료구조이다.

성질

1) 원소의 추가는 O(1)
2) 운소의 제거는 O(1)
3) 제일 앞/뒤의 원소 확인이 O(1)
4) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로는 불가능하다.
5) STL deque에서는 인덱스로 원소에 접근이 가능하다. (STL stack, STL queue는 안됨)

---

구현

덱은 배열 혹은 연결리스트로 구현을 할 수 있다.

#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();
}

STL queue으로 구현

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

int main(void){
  deque<int> DQ;
  DQ.push_front(10); // 10
  DQ.push_back(50); // 10 50
  DQ.push_front(24); // 24 10 50
  for(auto x : DQ)cout<<x;
  cout << DQ.size() << '\n'; // 3
  if(DQ.empty()) cout << "DQ is empty\n";
  else cout << "DQ is not empty\n"; // DQ is not empty
  DQ.pop_front(); // 10 50
  DQ.pop_back(); // 10
  cout << DQ.back() << '\n'; // 10
  DQ.push_back(72); // 10 72
  cout << DQ.front() << '\n'; // 10
  DQ.push_back(12); // 10 72 12
  DQ[2] = 17; // 10 72 17
  DQ.insert(DQ.begin()+1, 33); // 10 33 72 17
  DQ.insert(DQ.begin()+4, 60); // 10 33 72 17 60
  for(auto x : DQ) cout << x << ' ';
  cout << '\n';
  DQ.erase(DQ.begin()+3); // 10 33 72 60
  cout << DQ[3] << '\n'; // 60
  DQ.clear(); // DQ의 모든 원소 제거
}

1) 앞쪽과 뒷쪾의 추가/제거가 필요하면 vector 대신에 deque를 쓰면 좋지만 앞쪽/뒷쪽의 추가/제거가 필요하지 않고 배열 느낌으로 쓰고싶으면 vector 쓰는게 좋다.
2) deque을 보면 vector랑 비슷하게 느껴질 수 있지만 deque는 원소들이 메모리상에서 연속적으로 배치되어 있지 않은 차이점이 있다.