#include <iostream>
#include <memory>
#include <string>


template<typename T> class Deque {
 public:
  Deque(): current_capacity(8) {
    arr = malloc.allocate(current_capacity);
  }

  size_t size() const {
    return current_size;
  }

  void push_back(const T &item);
  void push_front(const T &item);
  T pop_front();
  T pop_back();

  T front() const {
    return *((arr + push_front_position) - 1);
  }

  T back() const {
    return *((arr + push_back_position) - 1);
  }

 private:
  T *arr = nullptr;
  void reallocate();
  size_t current_size = 0;
  size_t current_capacity;
  size_t push_back_position = (current_capacity / 2) + 1;
  size_t push_front_position = current_capacity / 2;
  static std::allocator<T> malloc;
};

template<typename T> std::allocator<T> Deque<T>::malloc;


template<typename T> void Deque<T>::reallocate() {
  T *new_arr = malloc.allocate(current_capacity * 2);

  std::uninitialized_copy(arr, arr + current_capacity, new_arr);

  for (size_t i = 0; i != current_capacity; ++i)
    malloc.destroy(arr + i);

  malloc.deallocate(arr, current_capacity);

  arr = new_arr;
  current_capacity = current_capacity * 2;
  push_back_position = (current_capacity / 2) + 1;
  push_front_position = current_capacity / 2;
}


template<typename T> void Deque<T>::push_back(const T &item) {
  if (current_size + 1 > current_capacity)
    reallocate();

  malloc.construct(arr + push_back_position, item);

  ++push_back_position;
  ++current_size;
}


template<typename T> void Deque<T>::push_front(const T &item) {
  if (current_size + 1 > current_capacity)
    reallocate();

  malloc.construct(arr + push_front_position, item);

  --push_front_position;
  ++current_size;
}


int main() {
  Deque<int> test;

  for (int i = 0; i <= 5; ++i)
    test.push_front(i);

  for (int i = 5; i <= 10; ++i)
    test.push_back(i);

  std::cout << test.front() << std::endl;
  std::cout << test.back() << std::endl;

  return 0;
}