一个数组实现两个栈-创新互联
题目:
网站制作、成都网站制作介绍好的网站是理念、设计和技术的结合。创新互联建站拥有的网站设计理念、多方位的设计风格、经验丰富的设计团队。提供PC端+手机端网站建设,用营销思维进行网站设计、采用先进技术开源代码、注重用户体验与SEO基础,将技术与创意整合到网站之中,以契合客户的方式做到创意性的视觉化效果。一个数组A[1..n]来实现两个栈,使得两个栈中的元素总和不到n时,两个都不会发生上溯。
思路(1):
创建一个数组,分别从两边开始,依次往中间走。
思路(2):
创建一个数组,一个走奇数位,一个走偶数位。
//奇偶方式 #define _CRT_SECURE_NO_WARNINGS #includeusing namespace std; template class TwoStack { public: TwoStack(int size) :_top1(-1), _top2(-1), _len(size) { _arr = new T[size]; } ~TwoStack() { if (_arr) { delete[] _arr; } } void Push(int index, int data); T Pop(int index); bool IsEmpty(int index); void Disp(); T Top(int index); private: int _top1; int _top2; int _len; T* _arr; }; template void TwoStack ::Push(int index, int data) { //if (_len % 2 == 0) //{ //if (_top1>_len-2 || _top2>=_len-1) //{ //cout << "overflow" << endl; //return; //} //} //else //{ //if (_top1 >_len || _top2 >= _len - 2) //{ //cout << "overflow" << endl; //return; //} //} int flag = _len % 2; if (index == 0) { if (flag == 0) { if (_top1 >= _len - 2) { cout << "Stack1 overflow" << endl; return; } } if (flag == 1) { if (_top1 >= _len - 1) { cout << "overflow" << endl; return; } } //////////////////////////// if (_top1 == -1) { _top1 = 0; _arr[_top1] = data; } else { _top1+=2; _arr[_top1] = data; } } ///////////////////////////////////////////////////////// else { if (flag == 0) { if (_top2 >= _len - 2) { cout << "Stack2 overflow" << endl; return; } } if (flag == 1) { if (_top2 >= _len - 1) { cout << "overflow" << endl; return; } } /////////////// if (_top2 == -1) { _top2 = 1; _arr[_top2] = data; } else { _top2+=2; _arr[_top2] = data; } } } template T TwoStack ::Pop(int index) { int ret; if (index == 0) { if (_top1 < 0) { cout << "Stack1 is null" << endl; return -1; } else { ret = _arr[_top1]; _top1-=2; } } else { if (_top2 <1) { cout << "Stack2 is null" << endl; return -1; } else { ret = _arr[_top2]; _top2-=2; } } return ret; } template bool TwoStack ::IsEmpty(int index) { if (index == 0 && _top1 < 0) return true; if (index == 1 && _top2 < 0) return true; return false; } template void TwoStack ::Disp() { { for (int i = 0; i < _len; i++) { cout << _arr[i] << " "; } } } template T TwoStack ::Top(int index) { if (0 == index && _top1 >= 0) { return _arr[_top1]; } if (1 == index && _top2 >=1) { return _arr[_top2]; } cout << "NO TOP" << endl; exit(0); } void test1() { TwoStack s(10); s.Push(0, 1); s.Push(0, 2); s.Push(0, 3); s.Push(0, 4); s.Push(0, 5); //s.Push(0, 5); s.Push(1, 6); s.Push(1, 7); s.Push(1, 8); s.Push(1, 9); s.Push(1, 10); //s.Push(1, 10); //cout << s.Top(1); //cout< s(10); s.Push(0, 1); s.Push(0, 2); s.Push(0, 3); s.Push(0, 4); s.Push(0, 5); s.Push(1, 6); s.Push(1, 7); s.Push(1, 8); s.Push(1, 9); s.Push(1, 10); cout << s.Pop(0)<<" "; cout << s.Pop(0) << " "; cout << s.Pop(0) << " "; cout << s.Pop(0) << " "; cout << s.Pop(0) << " "; cout << s.Pop(1) << " "; cout << s.Pop(1) << " "; cout << s.Pop(1) << " "; cout << s.Pop(1) << " "; cout << s.Pop(1) << " "; //cout< 一前一后向中间走:
#define _CRT_SECURE_NO_WARNINGS #includeusing namespace std; template class TwoStack { public: TwoStack(int size) :_top1(-1), _top2(size), _len(size) { _arr = new T[size]; } ~TwoStack() { if (_arr) { delete[] _arr; } } void Push(int index, int data); T Pop(int index); bool IsEmpty(int index); void Disp(); T Top(int index); private: int _top1; int _top2; int _len; T* _arr; }; template void TwoStack ::Push(int index, int data) { if (_top1 >= _top2 - 1) { cout << "Stack is overflow" << endl; return; } if (index == 0) { _top1++; _arr[_top1] = data; } else { _top2--; _arr[_top2] = data; } } template T TwoStack ::Pop(int index) { int ret; if (index == 0) { if (_top1 < 0) { cout<<"Stack1 is null"< _len) { cout << "Stack2 is null" << endl; return -1; } else { ret = _arr[_top2]; _top2++; } } return ret; } template bool TwoStack ::IsEmpty(int index) { if (index == 0 && _top1 < 0) return true; if (index == 1 && _top2 >= _len) return true; return false; } template void TwoStack ::Disp() { { for (int i = 0; i < _len; i++) { cout << _arr[i] << " "; } } } template T TwoStack ::Top(int index) { if (0 == index && _top1>=0) { return _arr[_top1]; } if (1 == index && _top2 < _len) { return _arr[_top2]; } cout << "NO TOP" << endl; exit(0); } void test1() { TwoStack s(10); s.Push(0, 1); s.Push(0, 2); s.Push(0, 3); s.Push(0, 4); s.Push(0, 5); //s.Push(0, 5); s.Push(1, 6); s.Push(1, 7); s.Push(1, 8); s.Push(1, 9); s.Push(1, 10); //s.Push(1, 10); s.Disp(); //cout << s.IsEmpty(1); } void test2() { TwoStack s(10); s.Push(0, 1); s.Push(0, 2); s.Push(0, 3); s.Push(0, 4); s.Push(0, 5); s.Push(1, 6); s.Push(1, 7); s.Push(1, 8); s.Push(1, 9); s.Push(1, 10); //cout< using namespace std; template class TwoStack { public: TwoStack() :_top1(-1), _top2(-1), _len(0), _arr(NULL), _capacity(0) { } ~TwoStack() { if (_arr) { delete[] _arr; } } void Push(int index, int data); T Pop(int index); bool IsEmpty(int index); void Disp(); T Top(int index); void IncreaseCapcity(); private: int _top1; int _top2; int _len; T* _arr; int _capacity; }; template void TwoStack ::IncreaseCapcity() { int top1 = _top1; int top2 = _top2; int size = _capacity; _capacity = _len * 2 + 3; int capacity = _len * 2 + 3; int newlen = capacity; T* tmp = new T[_capacity]; if (_arr != NULL) { for (int i = 0; i <= top1; i++) { tmp[i] = _arr[i]; } for (int j = top1 + 1; j < size; j++) { tmp[--capacity] = _arr[--_len]; --newlen; } } if (_arr != NULL) { delete[] _arr; } _arr = tmp; _len = newlen; _top2 = _len; } template void TwoStack ::Push(int index, int data) { if (_top1 >= _top2 - 1) { IncreaseCapcity(); } if (index == 0) { _top1++; _arr[_top1] = data; } else { _top2--; _arr[_top2] = data; } } template T TwoStack ::Pop(int index) { int ret; if (index == 0) { if (_top1 < 0) { cout<<"Stack1 is null"< _len) { cout << "Stack2 is null" << endl; return -1; } else { ret = _arr[_top2]; _top2++; } } return ret; } template bool TwoStack ::IsEmpty(int index) { if (index == 0 && _top1 < 0) return true; if (index == 1 && _top2 >= _len) return true; return false; } template void TwoStack ::Disp() { { for (int i = 0; i < _capacity; i++) { cout << _arr[i] << " "; } } } template T TwoStack ::Top(int index) { if (0 == index && _top1>=0) { return _arr[_top1]; } if (1 == index && _top2 < _len) { return _arr[_top2]; } cout << "NO TOP" << endl; exit(0); } void test1() { TwoStack s; s.Push(0, 1); s.Push(0, 2); s.Push(0, 3); s.Push(0, 4); s.Push(0, 5); //s.Push(0, 5); //cout << s.Pop(0) << " "; //cout << s.Pop(0) << " "; //cout << s.Pop(0) << " "; //cout << s.Pop(0) << " "; //cout << s.Pop(0) << " "; s.Push(1, 6); s.Push(1, 7); s.Push(1, 8); s.Push(1, 9); s.Push(1, 10); //s.Push(1, 10); s.Disp(); //cout << s.IsEmpty(1); } void test2() { TwoStack s; s.Push(0, 1); s.Push(0, 2); s.Push(0, 3); s.Push(0, 4); s.Push(0, 5); s.Push(1, 6); s.Push(1, 7); s.Push(1, 8); s.Push(1, 9); s.Push(1, 10); //cout< 创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
名称栏目:一个数组实现两个栈-创新互联
链接分享:http://pwwzsj.com/article/dpcddj.html