十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
用两个栈模拟队列的思想就是“倒水思想”,这里我们用自定义类型模拟出线性表,再用线性表做容器实现栈的数据结构,最后用栈来实现队列,代码如下:
扶余网站建设公司创新互联,扶余网站设计制作,有大型网站制作公司丰富经验。已为扶余数千家提供企业网站建设服务。企业网站搭建\外贸网站制作要多少钱,请找那个售后服务好的扶余做网站的公司定做!#include#include #include struct __TrueType//类型萃取 { bool Get() { return true; } }; struct __FalseType { bool Get() { return false; } }; template struct TypeTraits { typedef __FalseType __IsPODType; }; template <> struct TypeTraits< bool> { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< char> { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< unsigned char > { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< short> { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< unsigned short > { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< int> { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< unsigned int > { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< long> { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< unsigned long > { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< long long > { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< unsigned long long> { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< float> { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< double> { typedef __TrueType __IsPODType; }; template <> struct TypeTraits< long double > { typedef __TrueType __IsPODType; }; template struct TypeTraits< _Tp*> { typedef __TrueType __IsPODType; }; template //自定义类型实现线性表 class SeqList { public: SeqList() :_size(0), _capacity(10), _array(new T[_capacity]) { memset(_array, 0, sizeof(T)*_capacity); } SeqList(const T &x) :_size(1), _capacity(10), _array(new T[_capacity]) { _array[0] = x; } SeqList(const SeqList & x) { _array = new T[x._size]; my_memcpy(_array, x._array, sizeof(T)*x._size); _capacity = x._size; _size = _capacity; } void PushBack(const T & x) { _CheckCapacity(); _array[_size++] = x; } void PushFront(const T & x) { _CheckCapacity(); for (size_t i = _size; i > 1; i--) { _array[_size] = _array[_size - 1]; } _size++; _array[0] = x; } void PopBack() { _size--; } void PopFront() { assert(_size); for (size_t i = 0; i < _size - 1; i++) { _array[i] = _array[i + 1]; } _size--; } size_t Size() { return _size; } SeqList & operator = (SeqList l) { swap(_array, l._array); swap(_size, l._size); swap(_capacity, l._capacity); return *this; } ~SeqList() { if (_array) { delete[] _array; } } T& operator [] (const size_t t) { return _array[t]; } private: void _CheckCapacity() { if (_size >= _capacity) { _capacity *= 3; T * tmp = new T[_capacity]; memcpy(tmp, _array, sizeof(T)*_capacity); delete[] _array; _array = tmp; } } void my_memcpy(T* dst, const T* src, size_t size) { if (TypeTraits ::__IsPODType().Get()) { memcpy(dst, src, size*sizeof (T)); } else { for (size_t i = 0; i < size; ++i) { dst[i] = src[i]; } } } size_t _size; size_t _capacity; T *_array; }; template >//适配器实现栈 class Stack { public: void Push(const T & x) { _con.PushBack(x); } void Pop() { _con.PopBack(); } size_t Size() { return _con.Size(); } bool Empty() { return Size() == 0; } T&top() { return _con[Size() - 1]; } protected: Contianer _con; }; template >//以栈为适配器,实现队列 class Queue { public: bool Empty() { return (_InStack.Empty() && _OutStack().Empty()); } size_t Size() { return _InStack.Size() + _OutStack.Size(); } void Push(const T &x) { _InStack.Push(x); } void Pop() { size_t MoveCount = _InStack.Size() - 1; for (size_t iCount = MoveCount; iCount > 0; --iCount) { T temp = _InStack.top(); _OutStack.Push(temp); _InStack.Pop(); } _InStack.Pop(); while (false == _OutStack.Empty()) { T temp = _OutStack.top(); _InStack.Push(temp); _OutStack.Pop(); } } T& Front() { return _InStack.top(); } T& Back() { size_t MoveCount = _InStack.Size() - 1; for (size_t iCount = MoveCount; iCount > 0; --iCount) { T temp = _InStack.top(); _OutStack.Push(temp); _InStack.Pop(); } T ret = _InStack.top(); while (false == _OutStack.Empty()) { T temp = _OutStack.top(); _Instack.Push(temp); _OutStack.Pop(); } return ret; } void PrintQueue() { size_t MoveCount = _InStack.Size(); for (size_t iCount = MoveCount; iCount > 0; --iCount) { T temp = _InStack.top(); _OutStack.Push(temp); _InStack.Pop(); } while (false == _OutStack.Empty()) { T temp = _OutStack.top(); _InStack.Push(temp); cout << "<-" << temp; _OutStack.Pop(); } cout << endl; } private: container _InStack; container _OutStack; };
测试用例如下:
void Test() { Queueq1; q1.Push(1); q1.Push(2); q1.Push(3); q1.Push(4); q1.Push(5); q1.Push(6); q1.PrintQueue(); q1.Pop(); q1.PrintQueue(); }
如有什么不足或疑问,希望指教
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。