[ Implement Queue using Stacks ] 用堆疊實作佇列

一般在C++ STL中queue都是用deque實作的，而deque用和vector類似的倍增法來實作(稍微多了一些操作導致常數有點大但是每次操作時間較為平均)，雖然夠用但有些時候這不是一個好選擇。
大二資料結構期中考時，考了一題叫你用stack實作queue的方法，我那時候想了一下想了一個超帥的作法，需要用到兩個stack，我把它成為stack A和B。

• push:
  push時直接把資料push進B中，$\ord{1}$
• pop:
  這是個問題，我們把A的top當成是queue的front，所以直接把A pop就可以了，如果A是empty的話，就把B的資料依序pop然後push進A中，在進行該操作，均攤$\ord{1}$
• front:
  如pop所述，把A的top當成是queue的front，如果A是empty再另做處理，$\ord{1}$
• back:
  和front相反，把B的top當成是queue的back，如果B是empty再另做處理，$\ord{1}$

以下為實作過程，以c++ vector代替stack：

	#include<vector>
	template<typename T>
	class st_queue{
	std::vector<T> A,B;
	public:
	void swap(st_queue& stq){
	A.swap(stq.A);
	B.swap(stq.B);
	}
	bool empty()const{
	return A.empty()&&B.empty();
	}
	size_t size()const{
	return A.size()+B.size();
	}
	T &front(){
	return A.empty() ? B.front() : A.back();
	}
	T &back(){
	return B.empty() ? A.front() : B.back();
	}
	void push(const T& data){
	B.push_back(data);
	}
	void pop(){
	if(A.size()) A.pop_back();
	else{
	for(int i=int(B.size())-1;i>0;--i)
	A.push_back(B[i]);
	B.clear();
	}
	}
	};

view raw st_queue.cpp hosted with ❤ by GitHub