これは、アルゴリズム/インタビューの質問書で見つけたものです。他の誰かがこれについていくつかの投稿をしていましたが、まだいくつか質問があります。本の元のテキストとコードは次のとおりです。
implement 3 stacks using 1 array:
Approach 2:
このアプローチでは、配列に空き領域がある限り、任意のスタックを拡張できます。スタックにスペースを順番に割り当て、新しいブロックを前のブロックにリンクします。これは、スタック内の新しい要素は、その特定のスタックの前の最上位要素へのポインターを保持することを意味します。この実装では、未使用スペースの問題に直面します。たとえば、スタックがその要素の一部を削除した場合、削除された要素が配列の最後に表示されるとは限りません。したがって、その場合、新しく解放されたスペースを使用できなくなります。この欠点を克服するために、空きリストを維持することができ、配列全体のスペースが最初に空きリストに与えられます。挿入ごとに、空きリストからエントリを削除します。削除の場合は、空きセルのインデックスを空きリストに追加するだけです。
1 int stackSize = 300;
2 int indexUsed = 0;
3 int[] stackPointer = {-1,-1,-1};
4 StackNode[] buffer = new StackNode[stackSize * 3];
5 void push(int stackNum, int value) {
6 int lastIndex = stackPointer[stackNum];
7 stackPointer[stackNum] = indexUsed;
8 indexUsed++;
9 buffer[stackPointer[stackNum]]=new StackNode(lastIndex,value);
10 }
11 int pop(int stackNum) {
12 int value = buffer[stackPointer[stackNum]].value;
13 int lastIndex = stackPointer[stackNum];
14 stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous;
15 buffer[lastIndex] = null;
16 indexUsed--;
17 return value;
18 }
19 int peek(int stack) { return buffer[stackPointer[stack]].value; }
20 boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; }
21
22 class StackNode {
23 public int previous;
24 public int value;
25 public StackNode(int p, int v){
26 value = v;
27 previous = p;
28 }
29 }
私の質問は: メソッド pop() で、buffer[lastIndex] を null に設定した後 (15 行目)、次に indexUsed--(16 行目)、indexUsed は空のスペースの先頭になりますか? 最初のスタック : S1、2 番目のスタック : S2、3 番目のスタック : S3のスタック トップ ノードを呼び出しましょう。s1 をポップする前に s1 に続いて s2 と s3 をプッシュした場合、
index: 10 11 12 13
-------------------------------
| ... | s1 | s2 | s3 | null |
-------------------------------
indexUsedは現在 13 です。最初のスタックで pop() を実行する場合は、次のようになります。
index: 10 11 12 13
----------------------------------
| ... | null | s2 | s3 | null |
----------------------------------
indexUsedは現在 13-- 、つまり 12 です。新しいノードをこの配列にプッシュしたい場合は、push() メソッドに従って、7 行目で indexUsed が stackPointer に割り当てられ、次のように使用されます。インデックスを配列にプッシュすると、12番目のエントリのs3(stack3のトップノード)が上書きされませんか?
added:
それを機能させるにはどうすれば変更できますか？一見すると、boolean[] を実装してストレージ配列内の各エントリの使用状況を追跡することを考えますが、それは時間とスペースを消費します。
ありがとう！