《Cracking the Coding Interview》——第3章:栈和队列——题目1

时间:2022-12-14 22:26:18

2014-03-18 03:19

题目:用一个数组实现3个栈。

解法:

  首先我想过让三个栈动态决定长度。要么左右各一个向中间靠拢,要么三个穿插着,后来都觉得实现起来太复杂,而且思路总有各种功能缺陷,会导致额外的时间或空间复杂度。所以,还是三等分成固定大小吧。好写又好用。

代码:

// 3.1 Use an array to implement three stacks.
// three fixed-length stacks
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std; template <class T>
class ThreeStack {
public:
ThreeStack(size_t _total_capacity = ): total_capacity(_total_capacity) {
msize[] = ;
msize[] = ;
msize[] = ; mcapacity[] = mcapacity[] = mcapacity[] = total_capacity / ;
mcapacity[] += (total_capacity % != ? : );
mcapacity[] += (total_capacity % == ? : ); offset[] = ;
offset[] = offset[] + mcapacity[];
offset[] = offset[] + mcapacity[]; mdata.resize(total_capacity);
} ~ThreeStack() {
mdata.clear();
} void push(int idx, T val) {
if (msize[idx] == mcapacity[idx]) {
// this stack is full
return;
} mdata[offset[idx] + msize[idx]] = val;
++msize[idx];
} void pop(int idx) {
if (msize[idx] == ) {
return;
} --msize[idx];
} T top(int idx) {
if (msize[idx] == ) {
return mdata[-];
} return mdata[offset[idx] + msize[idx] - ];
} size_t size(int idx) {
return msize[idx];
}
private:
// total capacity of all stack
size_t total_capacity;
// starting offset for each stack
size_t offset[];
// capacities of the three stacks
size_t mcapacity[];
// sizes of the three stacks
size_t msize[];
// the data in the stacks
vector<T> mdata;
}; int main()
{
int n;
size_t idx;
int val;
char str[]; scanf("%d", &n);
ThreeStack<int> ts(n);
while (scanf("%s", str) == ) {
if (strcmp(str, "end") == ) {
break;
} else if (strcmp(str, "push") == ) {
scanf("%u%d", &idx, &val);
ts.push(idx, val);
} else if (strcmp(str, "pop") == ) {
scanf("%u", &idx);
ts.pop(idx);
} else if (strcmp(str, "top") == ) {
scanf("%u", &idx);
printf("top[%u] = %d\n", idx, ts.top(idx));
} else if (strcmp(str, "size") == ) {
scanf("%u", &idx);
printf("size[%u] = %u\n", idx, ts.size(idx));
}
} return ;
}