From 剑指Offer 何海涛 著
#include#include #include template class CStack { public: CStack(void); ~CStack(void); T& top(void); void push(const T&); void pop(void); private: std::queue queue1; std::queue queue2;};template CStack ::CStack() { }template CStack ::~CStack() { }template T& CStack ::top() { if(queue1.empty()) { if(queue2.empty()) { throw std::exception(); }#if __cplusplus >= 201103L queue1.swap(queue2);#else while(queue2.size() > 1) { T& t = queue2.front(); queue1.push(t); queue2.pop(); } T& t = queue2.front(); queue1.push(t); queue2.pop(); return t;#endif } while(queue1.size() > 1) { T& t = queue1.front(); queue2.push(t); queue1.pop(); } T& t = queue1.front(); queue2.push(t); queue1.pop(); return t;}template void CStack ::push(const T& value) { if(queue1.empty()) {#if __cplusplus >= 201103L queue1.swap(queue2);#else queue2.push(value); return;#endif } queue1.push(value); }template void CStack ::pop() { if(queue1.empty()) { if(queue2.empty()) { throw std::exception(); }#if __cplusplus >= 201103L queue1.swap(queue2);#else while(queue2.size() > 1) { T& t = queue2.front(); queue1.push(t); queue2.pop(); } queue2.pop(); return ;#endif } while(queue1.size() > 1) { T& t = queue1.front(); queue2.push(t); queue1.pop(); } queue1.pop();}
测试集:
templatevoid test(const T& actual, const T& expected) { std::cout << std::boolalpha << (actual == expected) << std::endl;}int main(int argc, char* argv[]) { CStack stack; try { stack.top(); } catch(std::exception& e) { std::cout << "true" << std::endl; } stack.push('a'); stack.push('b'); stack.push('c'); test(stack.top(), 'c'); stack.pop(); test(stack.top(), 'b'); stack.push('d'); test(stack.top(), 'd'); stack.pop(); stack.pop(); stack.pop(); try { stack.pop(); } catch(std::exception& e) { std::cout << "true" << std::endl; } return 0;}