特定のアイテムがスタックからポップされた回数をどのように数えることが可能ですか？

Question

私は、ランダムな要素を削除する必要がある要素のスタックを持っています（つまり、その要素とその特定の要素の間にあるすべての要素がポップされ、再度プッシュされます）。そして、要素がポップされるたびに、他の要素に対して先にポップされた回数を判断する必要があります。

私は長い間このことを続けてきました。 （スタックは動的です（つまり、要素は時々追加され、削除されます））。

Answer 1

を単独でリンクされて、私はスタックを格納します各ノードには、アクセスされた回数を表す整数を保持します。リンクリストをただ繰り返し処理は、1を追加する次に、あなたがあなた自身のポップ（O（n）を）書くことができる

| 5 | -> | 2 | -> | 3 | -> | 1 | -> | 7 | 
| 0 | -> | 0 | -> | 0 | -> | 0 | -> | 0 | 

：IE、上に5とスタック、7底にして作られた全くのアクセスは次のようになりませんでしょう訪問した各ノードの数にアクセスする（ポップするものは常にスタック内にあると仮定できる場合は、一度反復する必要がありますが、そうでなければ2回反復する必要があります）。 // 0

| 5 | -> | 2 | -> | 1 | -> | 7 | 
| 1 | -> | 1 | -> | 0 | -> | 0 | 

ポップ（7）戻り値：//が0

| 5 | -> | 2 | -> | 1 | 
| 2 | -> | 2 | -> | 1 | 

を返します。

（2）POP：// 2

| 5 | -> | 1 | 
| 3 | -> | 1 | 

プッシュ（6）戻り値：

| 6 | -> | 5 | -> | 1 | 
| 0 | -> | 3 | -> | 1 | 

ポップ（1）：// 1つの

| 6 | -> | 5 | 
| 1 | -> | 4 | 

ポップを返す（6 ）：//返品1

| 5 | 
| 4 | 

3 pop（5）：// Returns 4

Answer 2

私はあなたのことを正しく理解していれば、独自のスタック構造を持ち、特定の要素のプッシュとポップを数えたいと思っています。そのような場合、あなたはstructでデータをラップし、スタック店このstructのリスト（スタックの内部実装が何であれ）かもしれない：

struct stack_data { 
    unsigned push_count; 
    unsigned pop_count; 
    void *data; /* or whatever type the data is */ 
}; 

... 

void stack_push(/* stack argument */, struct stack_data *data) 
{ 
    ... 
    data->push_count++; 
} 

void stack_pop(/* stack argument */, struct stack_data *data) 
{ 
    ... 
    data->pop_count++; 
}