덱, STL deque

덱 : deque(Double Ended Queue)

• 양쪽 끝에서 삽입과 삭제가 모두 가능함

시간 복잡도

1. 원소 추가 : O(1)
2. 원소 제거 : O(1)
3. 제일 앞/뒤의 원소 확인 : O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
   => STL deque 에서는 인덱스로 원소에 접근이 가능함

구현 방법

• 스택과 큐처럼 배열, 링크드 리스트로 모두 구현가능

배열로 구현

const int mid = 1000005;
int dat[2*mid+1];
int head = mid;    // 가장 앞에 있는 원소의 인덱스
int tail = mid;    // 가장 뒤에 있는 원소의 인덱스 + 1

• head, tail 의 초기값이 mid 인 이유

  • 큐에서는 앞쪽에서는 제거만 발생하고 뒷쪽에서는 삽입만 발생하다보니, 배열 내에서 실제 큐에 들어간 원소들이 차지하는 공간이 점점 오른쪽으로 이동하면서 확장하는 모양이었다.

  • 하지만 덱은 양쪽에서 모두 삽입이 가능하다. 따라서 마치 여의봉처럼 양쪽으로 확장해야한다.

  • 그렇다면 별생각 없이 시작 지점을 0번지로 뒀을 경우 왼쪽으로 확장을 할 수가 없어서 큰일난다. 대신에 시작 지점을 배열의 중간으로 둬야한다.

  • 배열의 크기는 2*mid + 1 이고, head와 tail의 초깃값은 mid이다.

구현 코드

#include <iostream>
using namespace std;

const int MAX = 1000005;
int dat[2 * MAX + 1];
int head = MAX;
int tail = MAX; // 맨 마지작 원소 인덱스의 다음 인덱스를 저장 ( 맨 마지막 원소 인덱스 + 1)

// 맨앞 삽입
void push_front(int x) {
	dat[head - 1] = x;
	head--;
}

// 맨뒤 삽입
void push_back(int x) {
	dat[tail] = x;
	tail++;
}

// 맨앞 원소 삭제
void pop_front() {
	head++;
}

// 맨뒤 원소 삭제
void pop_back() {
	tail--;
}

// 맨앞 원소 데이터값 추출
int front(){
	return dat[head];
}

// 맨뒤 원소 데이터값 추룰
int back() {
	return dat[tail - 1];
}



int main(void)
{
	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
}

STL deque

STL vector 와의 유사함

• STL vector 에서 제공되는 기능을 STL stack 에서도 다 제공
• 심지어 deque 는 front에서도 O(1)에 추가와 제거가 가능하니 deque 이 vector 보다 상위호환이라는 생각이 들 수 있겠지만,
  vector와 달리 deque는 원소들이 메모리 상에 연속하게 배치되어 있지 않다.

앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하면 STL deque 을 사용하고,
굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고 싶다면 STL vector를 사용할 것!

메소드 종류

• 인덱싱 가능 ex) dq[2] = 17; // 인덱스 2에다 17할당
• push_front
• push_back
• pop_front
• pop_back
• empty
• size
• insert
• erase
• clear
• begin

예제

#include <iostream>
using namespace std;

int main(void){
  deque<int> dq;
  
  dq.push_front(10);
  dq.push_back(50);
  dq.push_front(24); // 24 10 50 
  
  for(auto x : dq)
    cout << x;
  
  if(dq.empty())
    cout << "dq is empty\n";
  else
    cout << "dq is not empty\n";
  
  dq.pop_front(); // 10 50
  dq.pop_back(); // 10
  
  cout << dq.back() << "\n";
  
  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   => being()+1 에다 33 삽입
  dq.insert(dq.begin()+4, 60) // 10 33 71 17 60
  
  for(auto x : dq)
    cout << x << ' ';
  cout << '\n';
  
  dq.erase(dq.begin() + 3); // 10 33 72 60 
  cout << dq[3] << '\n';
  
  dq.clear(); // 모든 원소 제거
}