Deque의 정의

• 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조

덱의 성질

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 앞/뒤의 원소 확인이 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

덱의 구현

• 초기화

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

• 앞뒤로 모두 확장할 가능성이 있기 때문에 MX의 2배로 길이를 잡고, MX(중간)에 head와 tail을 위치

• 구현 풀코드 (스택, 큐와 개념이 비슷하여 코드로 보고 이해하는 것이 빠름)

  void DequeBasic::solution() {
      int mx = 1000005;
      int head = mx, tail = mx;
      int arr[mx*2];
      
      int n = 0;
      cin >> n;
      
      while(n--) {
          string s;
          cin >> s;
          if (s == "push_front") {
              int x;
              cin >> x;
              head--;
              arr[head] = x;
          }
          else if (s == "push_back") {
              int x;
              cin >> x;
              arr[tail] = x;
              tail++;
          }
          else if (s == "pop_front") {
              if (tail - head == 0)
                  cout << -1 << '\\n';
              else {
                  cout << arr[head] << '\\n';
                  head++;
              }
          }
          else if (s == "pop_back") {
              if (tail - head == 0)
                  cout << -1 << '\\n';
              else {
                  cout << arr[tail-1] << '\\n';
                  tail--;
              }
          }
          else if (s == "size") {
              cout << tail - head << '\\n';
          }
          else if (s == "empty") {
              if (head - tail == 0)
                  cout << 1 << '\\n';
              else cout << 0 << '\\n';
          }
          else if (s == "front") {
              if (head - tail == 0)
                  cout << -1 << '\\n';
              else cout << arr[head] << '\\n';
          }
          else if (s == "back") {
              if (head - tail == 0)
                  cout << -1 << '\\n';
              else cout << arr[tail-1] << '\\n';
          }
      }
  }