栈以及两个栈实现一个队列
//数组版动态增长的栈 #pragma once template <class T> class stack { public : stack() :_top(NULL),_base(NULL),_size(0),_capacity(0) {} void PushStack(const T& x) { //判断栈是否已满 //插入 if(_size == _capacity) { _capacity = _capacity * 2 + 10; T* tmp = new T[_capacity]; memcpy(tmp,_base,sizeof(T)*_size); delete []_base; _base = tmp; _top = _base + _size - 1; } _top = _base +_size; *_top = x; _size++; } void PopStack() { //空 //一个 //两个及以上 if(_base == NULL) { cout<< "该栈为空"<<endl; } else if (_base == _top) { _top--; //_base = ; _size = 0; } else { _top--; _size--; } } T GetTop() { return *_top; } int GetSize() { return _size; } bool Empty() { if(_size == 0) return true ; else return false ; } private : T* _top; T* _base; int _size; int _capacity; }; //两个栈实现一个队列 template <class T> class stackqueue { public : void push(const T& x) { noemptyqueue.PushStack (x); } void pop() { while(noemptyqueue.GetSize ()) { emptyqueue.PushStack (noemptyqueue.GetTop ()); noemptyqueue.PopStack (); } emptyqueue.PopStack (); while(emptyqueue.GetSize ()) { noemptyqueue.PushStack (emptyqueue.GetTop ()); emptyqueue.PopStack (); } } private : stack<T> emptyqueue; stack<T> noemptyqueue; };