[CareerCup] 3.1 Implement Three Stacks using Array 使用数组来实现三个栈
数组 实现 Using Array 三个 3.1 Three CareerCup
2023-09-11 14:21:39 时间
3.1 Describe how you could use a single array to implement three stacks.
这道题让我们用一个数组来实现三个栈,书上给了两种方法,第一种方法是定长分割 Fixed Division,就是每个栈的长度相同,用一个公用的一位数组buffer来保存三个栈的内容,前三分之一为第一个栈,中间三分之一为第二个栈,后三分之一为第三个栈,然后还要分别记录各个栈当前元素的个数,然后再分别实现栈的基本操作push, pop, top 和 empty,参见代码如下:
class ThreeStacks { public: ThreeStacks(int size) : _stackSize(size) { _buffer.resize(size * 3, 0); _stackCur.resize(3, -1); } void push(int stackIdx, int val) { if (_stackCur[stackIdx] + 1 >= _stackSize) { cout << "Stack " << stackIdx << " is full!" << endl; } ++_stackCur[stackIdx]; _buffer[stackIdx * _stackSize + _stackCur[stackIdx]] = val; } void pop(int stackIdx) { if (empty(stackIdx)) { cout << "Stack " << stackIdx << " is empty!" << endl; } _buffer[stackIdx * _stackSize + _stackCur[stackIdx]] = 0; --_stackCur[stackIdx]; } int top(int stackIdx) { if (empty(stackIdx)) { cout << "Stack " << stackIdx << " is empty!" << endl; } return _buffer[stackIdx * _stackSize + _stackCur[stackIdx]]; } bool empty(int stackIdx) { return _stackCur[stackIdx] == -1; } private: int _stackSize; vector<int> _buffer; vector<int> _stackCur; };
第二种方法是灵活分割 Flexible Divisions,这种方法较为复杂,这里就不细写了。
相关文章
- Java实现 LeetCode 643 子数组最大平均数 I(滑动窗口)
- Java实现 LeetCode 912 排序数组(用数组去代替排序O(N))
- Java实现 LeetCode 421 数组中两个数的最大异或值
- Java实现 LeetCode 384 打乱数组
- Java实现 LeetCode 209 长度最小的子数组
- Java实现 LeetCode 153 寻找旋转排序数组中的最小值
- Java实现 LeetCode 33 搜索旋转排序数组
- java实现数组转置
- Java实现 蓝桥杯 算法训练 删除数组零元素
- Java实现 蓝桥杯 算法训练 寻找数组中最大值
- Java数组转成list,list转数组
- leetcode - 子数组最大平均值
- 数据结构与算法01 之数组
- LeetCode-907. 子数组的最小值之和【单调栈,数组】
- 【华为OD机试Python实现】HJ93 数组分组(较难)
- 【LeetCode Python实现】33. 搜索旋转排序数组(中等)
- NC77 调整数组顺序使奇数位于偶数前面(一)
- js 创建二维数组
- CodeForces 396C 树状数组 + DFS
- 剑指 Offer 03. 数组中重复的数字