#ifndef _stack_sutter_
#define _stack_sutter_
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<stdexcept>
#include<memory>


template<typename T,typename Allocator = std::allocator<T> > 
struct  Stack_impl :public Allocator{
 
  size_t _top;
  size_t _size;
  T* _buffer;

  Stack_impl(size_t n):
    _top(0), 
    _size(n),
    _buffer(Allocator::allocate(_size)) {};
  
  ~Stack_impl() {
    for(size_t i=0;i<_top;++i)
      destroy(_buffer++);

    deallocate(_buffer,_size);
  }

  void swap(Stack_impl& rhs) throw() {
    std::swap(_buffer,rhs._buffer);
    std::swap(_size,rhs._size);
    std::swap(_top,rhs._top);
  }
};


template<typename T,size_t N = 10,typename Allocator = std::allocator<T> > class Stack {
private:
  Stack_impl<T,Allocator> _impl;

public:
  Stack(size_t n = N):_impl(n) {};

  Stack(const Stack& rhs):_impl(rhs._impl) {
    while(_impl._top < rhs._impl._top) {
      _impl.construct(_impl._buffer+_impl._top, rhs._impl._buffer[_impl._top]);
      ++_impl._top;
    }
  } 
  
  Stack &operator=(const Stack& rhs) {
    Stack tmp(rhs);
    _impl.swap(tmp._impl);
    return *this;
  }

  void push(const T &elem) {
    if(_impl._top==_impl._size) {

      Stack tmp(_impl._size+N);
      while(tmp._impl._top < _impl._top) {
	_impl.construct(tmp._impl._buffer+tmp._impl._top, 
		  _impl._buffer[tmp._impl._top]);
	++tmp._impl._top;
      }
      _impl.swap(tmp._impl);
    }
    
    _impl.construct(_impl._buffer+_impl._top,elem);
    ++_impl._top;
  }
  

  T &top() {
    if(_impl._top==0)
      throw std::domain_error("empty stack");
    return _impl._buffer[_impl._top-1];
  }


  void pop() {
    if(_impl._top==0)
      throw std::domain_error("empty stack");
    
    --_impl._top;
    _impl.destroy(_impl._buffer+_impl._top);
  }

  bool is_empty() {
    return _impl._top==0;
  }

};

#endif