#include <iostream>


using namespace std;

template<typename T>
class My_Simple_Node {
        T node_Value;
        My_Simple_Node<T>* nextNode;
        My_Simple_Node<T>* prevNode;
public:
        My_Simple_Node(T _node_value) : node_Value(_node_value), nextNode(0), prevNode(0) {}
        template<typename T> friend class My_Simple_iterator;
        template<typename T> friend class My_Simple_stack;
};


template<typename T>
class My_Simple_iterator {
private:
        My_Simple_Node<T>* current;
public:
        My_Simple_iterator(My_Simple_Node<T>* argument) : current(argument){}

        T& operator*() { return current->node_Value; }
        bool operator==(const My_Simple_iterator<T>& argument) { return current == argument.current; }
        bool operator!=(const My_Simple_iterator<T>& argument) { return current != argument.current; }

        My_Simple_iterator<T>& operator++(int)  {//후위++
                My_Simple_iterator<T>* return_Value = this;
                current = current->nextNode;
                return *return_Value;
        }

        My_Simple_iterator<T>& operator--(int) {//후위 --
                My_Simple_iterator<T>* return_Value = this;        
                current = current->prevNode;
                return *return_Value;
        }

        My_Simple_iterator<T>& operator++() {//전위++
                current = current->nextNode;
                return *this;
        }

        My_Simple_iterator<T>& operator--() {//후위--
                current = current->prevNode;
                return *this;
        }

        My_Simple_iterator<T>& operator-(int _minuse) {//후위--
                while (_minuse--)
                        this--;
                return *this;
        }

        My_Simple_iterator<T>& operator+(int _plus) {//후위--
                while (_plus--)
                        this++;
                return *this;
        }

};

template<typename T>
class My_Simple_stack {
private:
        class Node;
        
        typedef T* reference_type;
        typedef T value_type;
        typedef My_Simple_Node<T>* reference_node_type;
        typedef My_Simple_Node<T> node_type;

        size_t sz;
        reference_node_type head;
        reference_node_type tail;
public:

        typedef My_Simple_iterator<T> iterator;

        explicit My_Simple_stack() : sz(0), head(NULL),tail(NULL) {}

        explicit My_Simple_stack(My_Simple_stack<value_type>& argument) {
                for (My_Simple_stack<value_type>::My_Simple_iterator it = argument.begin();
                        it != argument.end(); it++)
                        this->push_back(*it);
        }

        value_type front() {
                return head->node_Value;
        }

        value_type top() {
                return tail->node_Value;
        }

        value_type pop_front() {
                value_type return_Value = head->node_Value;
                head = head->nextNode;
                delete head->prevNode;
                head->prevNode = NULL;
                sz--;
                return return_Value;
        }

        value_type pop_back() {
                value_type return_Value = tail->node_Value;
                tail = tail->prevNode;
                delete tail->nextNode;
                tail->nextNode = NULL;
                sz--;
                return return_Value;
        }

        iterator begin() {
                return iterator(head);
        }

        iterator end() {
                return iterator(0);
        }

        void push_back(value_type& v) {
                reference_node_type insert_node = new My_Simple_Node<T>(v);
                if (sz == 0) { head = tail = insert_node; }
                else if (sz == 1) {
                        head->nextNode = insert_node;
                        insert_node->prevNode = head;
                        tail = insert_node;
                }else{
                        tail->nextNode = insert_node;
                        insert_node->prevNode = tail;
                        tail = insert_node;
                }
                sz++;
        }

        void push_front(value_type& v) {
                reference_node_type insert_node = new My_Simple_Node<T>(v);
                if (sz == 0) { head = tail = insert_node; }
                else if (sz == 1) {
                        tail->prevNode = insert_node;
                        insert_node->nextNode = tail;
                        head = insert_node;
                }
                else {
                        head->prevNode = insert_node;
                        insert_node->nextNode = head;
                        head = insert_node;
                }
                sz++;
        }

        void clear() {
                while (head->nextNode) {
                        reference_node_type del_obj = head;
                        head = head->nextNode;
                        delete del_obj;
                }
                delete head;
                head = tail = NULL;
                sz = 0;
        }

        size_t size() { return sz; }
};

int main() {
        //use stack function
        return 0;
}


iterator 패턴이 무조껀 외부에서 접근해서 안에 STL 라이브러리들이 


typedef iterator_class<T> iterator


inline iterator& begin() { return iterator(head); }

inline iterator& end() { return iterator(NULL); }


정의되있어야 한다는데 그럼 각각 node들에 대한 firend 처리는 어떻게되는거지


걍 STL 상위 상속받는 parent class 가있어서 데이터하고 prev next저장하는 노드클래스가 그클래스에 friend선언되있는건가??


그리고 링크드리스트는 삽입삭제가 쉽다는건 알겠는데 random access 로 접근되는 vector기반 자료구조들은 insert하고 erase가 어떻게 구현되있는거지


삽입삭제시에 다시 allocator로 다시 재할당하나?? 존나비효율적일거같은뎅