重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
以前,我们实现一个栈,轻轻松松,无需考虑太多因素,即可实现。
创新互联公司-专业网站定制、快速模板网站建设、高性价比高阳网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式高阳网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖高阳地区。费用合理售后完善,10年实体公司更值得信赖。现在,要求在一个数组里实现两个栈,那么在数组里怎么实现栈呢?
无非就是下标索引,方法也不局限一种,例如:用奇数下标作为栈s1的结构,用偶数作为s2的结构;再者:一前一后的结构,栈s1从前往后,栈s2从后往前。
本人只想到了使用这两中方法实现,当然,这两种方法各有利弊。
第一种方法,倘若其中一个栈只入了一个元素,而另一个入了很多元素,那么会造成内存碎片,但是此方法有利于数组增容;
第二种方法,空间利用率很高,但是不有利于数组增容。
虽然各有利弊,但是实现的机制相同。
在这里,使用第一种方法实现:
#includeusing namespace std; template class arrayWithTwoStack { public: arrayWithTwoStack(int size) : top1(-1) , top2(-1) , _size(size) { _array = new T[size + 1]; } ~arrayWithTwoStack() { if (_array) { delete[] _array; } } public: void Push(int index, T data) { if (_size % 2 == 0) { if ((top1 > _size - 2) || (top2 >= _size - 1)) { cout << "Stack is overflow!" << endl; return; } } else { if ((top1 > _size - 1) || (top2 >= _size - 2)) { cout << "Stack is overflow!" << endl; return; } } 0是一号栈, 1是二号栈 if (index == 0) { if (top1 == -1) { top1 = 0; _array[top1] = data; } else { top1 += 2; _array[top1] = data; } } if (index == 1) { if (top2 == -1) { top2 = 1; _array[top2] = data; } else { top2 += 2; _array[top2] = data; } } } T Pop(int index) { int ret; if (index == 0) { if (top1 < 0) { return -1; cout << "Stack is underflow!" << endl; } else { ret = _array[top1]; top1 -= 2; } } if (index == 1) { if (top2 < 1) // top2从下标为1开始 { return -1; cout << "Satck is underflow!" << endl; } else { ret = _array[top2]; top2 -= 2; } } return ret; } T top(int index) // 返回栈顶元素 { if (index == 0 && top1 >= 0) { return _array[top1]; } if (index == 1 && top2 >= 1) { return _array[top2]; } cout << "No Top!" << endl; exit(0); } bool isEmpty(int index) { if (index == 0 && top1 < 0) return false; if (index == 1 && top2 < 1) return false; return true; } void Show() { if (top1 < 0 && top2 < 1) { cout << "Stack has no data!" << endl; return; } else { for (int i = 0; i < _size; i++) cout << _array[i] << " "; } cout << endl; } private: T top1; T top2; int _size; T* _array; }; int main() { arrayWithTwoStack s(10); s.Push(0, 0); s.Push(0, 2); s.Push(0, 4); s.Push(1, 1); s.Push(1, 3); s.Push(1, 5); s.Push(1, 7); s.Push(0, 6); s.Push(0, 8); s.Push(1, 9); s.Push(0, 10); s.Show(); cout << s.Pop(0) << " "; cout << s.Pop(0) << " "; cout << s.Pop(0) << " "; cout << s.Pop(0) << endl; cout << s.Pop(1) << " "; cout << s.Pop(1) << " "; cout << s.Pop(1) << " "; cout << s.Pop(1) << endl; cout << s.top(0) << endl; cout << s.top(1) << endl; s.Pop(0); cout << (s.isEmpty(0) ? "Yes" : "No") << endl; cout << (s.isEmpty(1) ? "Yes" : "No") << endl; system("pause"); return 0; }
若有纰漏,欢迎指正。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。