Что изменяет Алгоритм Гарвика точно?

Question

Алгоритм Гарвика - это алгоритм обработки переполнения стека. Я знаю, что такое оригинальный алгоритм и как он работает. Тем не менее, есть модифицированный алгоритм Гарвика, и у меня есть очень неопределенное описание этого «даже стеки растут в левом направлении, а нечетные стеки в правильном направлении».

Иллюстрацией модифицированного алгоритма из моей лекции является следующее, что также очень неопределенно.

Может кто-нибудь поможет дать более подробную информацию об этом модифицированном алгоритме, или предоставить некоторые ссылки? Спасибо!

Answer 1

Если вам нужно положить 2 стека в массив, то вы можете положить один стек в начале массива, расти вверх, когда вы нажимаете на элементы, и один стек в конце, растущий вниз.

Таким образом, вам не нужно беспокоиться о перераспределении свободного места, когда один из них заполняют, потому что они оба используют свободное пространство же, и вы можете свободно нажать на либо стеков, пока весь массив не будет полный.

Модифицированный алгоритм Гарвика, на который вы ссылаетесь, расширяет эту идею до более чем 2 стеков. С оригинальным алгоритмом Гарвика массив делится на N сегментов, и каждый сегмент имеет один стек, причем все стеки растут в одном направлении. В модифицированной версии массив делится на N/2 сегменты, и каждый сегмент имеет стеки, один растет вверх от начала сегмента и один растет вниз от конца.

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