[学習アルゴリズム]実戦アルゴリズム7強-DE

私がバーク金督がアップロードした「実戦アルゴリズム」のビデオを見て勉強した過程を記録します.
すべての写真は巴金督のブログから持ってきたものです.
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キュー実装

#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の違いは要素がメモリに連続的に配置されていないことです.