[알고 공부] 0x07강 - 덱

출처: 바킹독 https://blog.encrypted.gg/935

 

덱 (deque,  Double Ended Queue)

양쪽 끝에서 삽입과 삭제가 전부 가능

 

제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

독특하게도 STL deque에서는 인덱스로 원소에 접근 O (STL stack, queue에서 불가능)

 

배열, 연결리스트 구현 가능 -> 역시 배열이 쉽다.

원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개 (큐와 같음)

 

시작 지점이 0이면 왼쪽으로 확장이 안됨. 중간으로 둬야함

=> 배열 크기 2 * MX+1 이고 head와 tail의 초기값이 0이 아니라 MX 

 

직접 구현

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];
}

 

STL deque

#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의 모든 원소 제거
}

double ended queue라는 느낌보다는 vector랑 비슷

vector와 달리 deque은 모든 원소들이 메모리 상에 연속하게 배치 X

 

앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요 => STL deque

필요없고 배열같이 쓰고 싶다 => STL vector

 

https://cplusplus.com/reference/deque/deque/