Как можно посчитать, сколько раз конкретный предмет был вытолкнут из стека?

Question

У меня есть стек элементов, из которых должен быть удален случайный элемент (то есть все элементы, которые находятся между вершиной и этим конкретным элементом, будут вытолкнуты и сдвинуты снова)И каждый раз, когда элемент извлекается, мы должны определить, сколько раз он был извлечен ранее для других элементов.

Я давно этим занимаюсь.(Стек динамический (т.е. элементы добавляются и время от времени удаляются)).

Answer 1

Если я вас правильно понимаю, у вас есть своя собственная структура стека, и вы хотите подсчитать толчки и всплески определенных элементов.Если это так, вы можете обернуть ваши данные в 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++;
}

Answer 2

Я бы сохранил стек как односвязный список и сохранил бы целое число в каждом узле, чтобы представлять количество обращений к нему. IE, стек с 5 сверху, 7 снизу и без доступа, будет выглядеть так:

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

Тогда вы могли бы написать свой собственный pop (O (n)), который просто перебирает связанный список, добавляя 1 к счетчику доступа для каждого узла, который он посещает (если вы можете предположить, что то, что вы извлекаете, всегда находится в стеке, нужно выполнить итерацию только один раз, в противном случае вам может понадобиться выполнить итерацию дважды), так что pop (3): // возвращает 0

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

pop (7): // Возвращает 0

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

pop (2): // Возвращает 2

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

толчок (6):

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

pop (1): // Возвращает 1

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

pop (6): // Возвращает 1

| 5 |
| 4 |

pop (5): // Возвращает 4