#include <boost/circular_buffer.hpp>

template <typename T, int N>

class NodeStack

{

using DataT = std::array<T*,N>;

using iterator = typename DataT::iterator;

using const_iterator = typename DataT::const_iterator;

static const int split_size = N / 2;

NodeStack() :

cursor_{ nodes_.begin() }

{}

template <typename TInput>

NodeStack(TInput srcBegin, TInput srcEnd) :

cursor_{ nodes_.begin() + std::distance(srcBegin, srcEnd) }

{

std::copy(srcBegin, srcEnd, nodes_.begin());

}

// Other must be full

NodeStack(NodeStack& other, SplitTag) :

cursor_{ nodes_.begin() + split_size }

{

std::copy(other.nodes_.begin() + split_size, other.nodes_.end(), nodes_.begin());

other.cursor_ = other.nodes_.begin() + split_size;

}

void Push(T* e) { *cursor_ = e; ++cursor_; }

T* Pop() { --cursor_; return *cursor_; }

bool IsFull() const { return cursor_ == nodes_.end(); }

bool IsEmpty() const { return cursor_ == nodes_.begin(); }

iterator begin() { return nodes_.begin(); }

const_iterator begin() const { return nodes_.begin(); }

iterator end() { return cursor_; }

const_iterator end() const { return cursor_; }

DataT nodes_;

iterator cursor_;

};

back_{ nodes_.begin() + size_}