首页 > 代码库 > Careercup | Chapter 3

Careercup | Chapter 3

2024-07-07 19:22:37   230人阅读

3.1 Describe how you could use a single array to implement three stacks.

Flexible Divisions的方案，当某个栈满了之后，需要把相邻的栈调整好，这是一个递归的过程。

每个stack有一些属性，所以不妨将每个stack封闭起来，我这里是用一个private的struct来实现，方便，同时对外部又不可见。

对于一些常用的操作，比如环形数组取下一个数，前一个数，都可以封装起来。

  1 class XNStack {
  2 public:
  3     XNStack(int n, int capacity) : stackTotal(n), capacity(capacity), total(0) {
  4         buff = new int[capacity];
  5         stacks = new XStackData[n];
  6         for (int i = 0; i < n; ++i) {
  7             stacks[i].top = i * capacity / n;
  8             stacks[i].capacity = capacity / n;
  9             stacks[i].size = 0;
 10         }
 11         if (capacity % n) stacks[n - 1].capacity++;
 12     }
 13     
 14     ~XNStack() {
 15         delete[] buff;
 16         delete[] stacks;
 17     }
 18 
 19     void push(int stackNum, int v) {
 20         cout << "push " << stackNum << " " << v << endl;
 21         if (total >= capacity) {
 22             cout << "full" << endl;
 23             return; // full
 24         }
 25         total++;
 26         if (stacks[stackNum].size < stacks[stackNum].capacity) {
 27             buff[stacks[stackNum].top] = v;
 28             stacks[stackNum].top = next(stacks[stackNum].top);
 29             stacks[stackNum].size++;
 30         } else {
 31             int n = stackNum + 1;
 32             if (n >= stackTotal) n = 0;
 33             shift(n);
 34             buff[stacks[stackNum].top] = v;
 35             stacks[stackNum].top = next(stacks[stackNum].top);
 36             stacks[stackNum].size++;
 37             stacks[stackNum].capacity++;
 38         }
 39     }
 40 
 41     void pop(int stackNum) {
 42         cout << "pop " << stackNum << endl;
 43         if (stacks[stackNum].size < 1) {
 44             cout << "empty" << endl;
 45             return;
 46         }
 47         total--;
 48         stacks[stackNum].size--;    
 49         stacks[stackNum].top = pre(stacks[stackNum].top);    
 50     }
 51 
 52     int top(int stackNum) {
 53         return buff[pre(stacks[stackNum].top)];
 54     }
 55 
 56     bool empty(int stackNum) const {
 57         return stacks[stackNum].size == 0;
 58     }
 59 
 60     void print() {
 61         for (int i = 0; i < stackTotal; ++i) {
 62             cout << "stack[" << i << "]: size[" << stacks[i].size << "] capacity[" << stacks[i].capacity << "] top[" << stacks[i].top << "]" << endl;
 63         }
 64 
 65         for (int i = 0; i < capacity; ++i) {
 66             cout << buff[i] << " ";
 67         }
 68         cout << endl;
 69     }
 70 
 71 private:
 72     struct XStackData {
 73         int top;
 74         int capacity;
 75         int size;
 76     };
 77     
 78     int next(int i) {
 79         i++;
 80         if (i >= capacity) i = 0;
 81         return i;
 82     }
 83 
 84     int pre(int i) {
 85         i--;
 86         if (i < 0) i = capacity - 1;
 87         return i;
 88     }
 89 
 90     void shift(int stackNum) {
 91         if (stacks[stackNum].size >= stacks[stackNum].capacity) {
 92             int next = stackNum + 1;
 93             if (next >= stackTotal) next = 0;
 94             shift(next);
 95         } else {
 96             stacks[stackNum].capacity--;
 97         }
 98         int j = stacks[stackNum].top;
 99         for (int i = 0; i < stacks[stackNum].capacity; ++i) {
100             int p = pre(j); 
101             buff[j] = buff[p];
102             j = p;
103         }
104         stacks[stackNum].top = next(stacks[stackNum].top);
105     }
106     int *buff;
107     XStackData *stacks;
108     int capacity;
109     int total;
110     int stackTotal;
111 };

 


联系
我们