Cracking Coding Interview - 3.1 Three in One

Three in One: Describe how you could use a single array to implement three stacks.

Hints: #2, #12, #38, #58

解答

如果数组的长度固定,那么可以把数组分割成3份,每份各司其职。不过这个似乎太简单了。

如果说不固定3个数组的长度,即抢占式的。那么似乎每个stack都记录自己的element的下标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Stack {
  private Object[] array;
  private int[] elementIndex;
  private int size;
  
  public Stack(Object[] array) {
    this.array = array;
    this.elementIndex = new int[array.length];
    for (int i = 0; i < elementIndex.length; i++) {
      elementIndex[i] = -1;
    }
  }
  
  public Object peek() {
    if (isEmpty()) {
      return null;
    }
    int slot = elementIndex[size - 1];
    return array[slot];
  }
  
  public boolean push(Object value) {
    int slot = -1;
    for (int i = 0; i < array.length; i++) {
      if (array[i] == null) {
        slot = i;
        break;
      }
    }
    if (slot == -1) {
      return false;
    }
    array[slot] = value;
    elementIndex[size] = slot;
    size++;
    return true;
  }
  
  public Object pop() {
    if (isEmpty()) {
      return null;
    }
    int slot = elementIndex[size - 1];
    Object data = array[slot];
    array[slot] = null;
    elementIndex[size - 1] = -1;
    size--;
    return data;
  }
  
  public boolean isEmpty() {
    return size == 0;
  }
}

版权

评论