#ifndef QUEUE_H_
#define QUEUE_H_

namespace std {
	template <class T>
	class queue {
		// 僐僺乕僐儞僗僩儔僋僞梡朄嬛巭
		queue(queue& org) {}
		// 僐僺乕戙擖墘嶼巕梡朄嬛巭
		void operator =(queue& org) {}
		
	protected:
		T* pt_; // 摦揑偵妱傝摉偰偨攝楍傊偺億僀儞僞
		size_t capacity_; // 妱傝摉偰嵪傒偺攝楍僒僀僘
		size_t elements_; // 奿擺偟偨梫慺悢
		dword increase_; // 攝楍憹壛暘
		dword findex_; // 梫慺捛壛梡
		dword bindex_; // 梫慺庢摼梡
		// findex_傪bindex_偑捛偄偐偗傞巇慻傒(儕儞僌僶僢僼傽)
		
		/*
		 * 椺1 晛捠1
		 * 僨乕僞 仩仩仭仭仭仭仭仭仭仩仩仩
		 *            仾            仾
		 *          bindex_       findex_
		 * 
		 * 椺2 晛捠2
		 * 僨乕僞 仭仭仩仩仩仩仩仭仭仭仭仭
		 *            仾        仾
		 *          findex_   bindex_
		 * 
		 * 椺3 枮攖
		 * 僨乕僞 仭仭仭仭仭仭仭仭仭仭仭仭
		 *                  仾
		 *            findex_,bindex_
		 */
		
		/*
		 * 僉儍僷僔僥傿傪峀偘傞
		 */
		void expand();
		
	public:
		/*
		 * 堷悢晅偒寭僨僼僅儖僩僐儞僗僩儔僋僞
		 */
		explicit
		queue(int capacity = 5, int increase = 5);
		
		/*
		 * 僨僼僅儖僩僨僗僩儔僋僞
		 */
		virtual ~queue();
		
		/*
		 * 梫慺悢傪曉偡
		 */
		inline size_t size() const;
		
		/*
		 * 嵟戝梫慺悢傪曉偡
		 */
		inline size_t max_size() const;
		
		/*
		 * 攝楍偑嬻偐偳偆偐
		 */
		bool empty() const;
		
		/*
		 * 枛旜偵梫慺傪捛壛
		 */
		void push(const T& x);
		
		/*
		 * 愭摢梫慺傪嶍彍
		 */
		void pop();
		
		/*
		 * 愭摢梫慺傪嶲徠
		 */
		T& front();
		
		/*
		 * 枛旜梫慺傪嶲徠
		 */
		T& back();
	};

	template <class T>
	void queue<T>::expand() {
		// increase_暘僉儍僷僔僥傿傪峀偘傞
		capacity_ += increase_;
		
		// 怴偟偄攝楍傪摦揑偵妋曐
		T* newpt_ = new T[capacity_];
		
		if(bindex_ < findex_) {
			// 晛捠1
			// 僨乕僞傪怴偟偄攝楍偵僐僺乕
			dword i;
			for(i = 0; i < elements_; i++) {
				newpt_[bindex_ + i] = pt_[bindex_ + i];
			}
		} else if(findex_ <= bindex_) {
			// 晛捠2 寭 枮攖
			// 僨乕僞傪怴偟偄攝楍偵僐僺乕
			dword i;
			for(i = 0; i < findex_; i++) {
				newpt_[i] = pt_[i];
			}
			for(i = bindex_; i < capacity_; i++) {
				newpt_[increase_ + i] = pt_[i];
			}
			bindex_ += increase_;
		}
		
		delete[] pt_;
		pt_ = newpt_;
	}
	
	template <class T>
	queue<T>::queue(int capacity, int increase) {
		// 僉儍僷僔僥傿傪愝掕 嵟掅抣5
		capacity_ = capacity > 1 ? capacity : 1;
		// 憹壛暘愝掕
		increase_ = increase > 0 ? increase : 5;
		
		capacity_ = capacity;
		increase_ = increase;
		
		// 攝楍傪摦揑偵妋曐
		pt_ = new T[capacity_];
		
		// 嬻偺抣T()偱弶婜壔
		for(dword i = 0; i < capacity_; i++) {
			pt_[i] = T();
		}
		
		// findex_偲bindex_傪愭摢丄枛旜偵愝掕
		findex_ = 0;
		bindex_ = 0;
	}
	
	template <class T>
	queue<T>::~queue() {
		delete[] pt_;
	}
	
	template <class T>
	size_t queue<T>::size() const {
		return elements_;
	}
	
	template <class T>
	size_t queue<T>::max_size() const {
		return capacity_;
	}
	
	template <class T>
	bool queue<T>::empty() const {
		return elements_ == 0 ? true : false;
	}
	
	template <class T>
	void queue<T>::push(const T& x) {
		if(findex_ == capacity_) {
			// 儕儞僌偺愭摢偵栠傞
			findex_ = 0;
		}
		if(elements_ == capacity_) {
			// 枮僞儞偵側偭偰偟傑偭偨
			expand();
		}
		pt_[findex_++] = x;
		elements_++;
	}
	
	template <class T>
	void queue<T>::pop() {
		if(elements_ > 0) {
			pt_[bindex_++] = T();
			elements_--;
			if(bindex_ == capacity_) {
				// 儕儞僌偺愭摢偵栠傞
				bindex_ = 0;
			}
		}
	}
	
	template <class T>
	T& queue<T>::front() {
		return pt_[findex_ - 1];
	}
	
	template <class T>
	T& queue<T>::back() {
		return pt_[bindex_];
	}
	
}

#endif /*QUEUE_H_*/
