Стек (stack) является одной из базовых структур хранения данных. Организуется по принципе LIFO (last in first out) т.е. первый пришел, последний вышел. Чаще всего при программировании реализуется с помощью массива и указателя на верхушку стека. При внесении данных (push) элемента записывается в верхушку стека, а указатель увеличивается на единицу. При извлечении данных (pop) элемент извлекается из верхушки стека, а указатель уменьшается на единицу.
Работает все нормально до тех пор, пока количество помещаемых данных не превышает длину выделенного для хранения стека массива. Возникает переполнение стека. Исправить это можно заранее выделив больший объем памяти. Но это не рационально с точки зрения использования памяти. Вполне логичным было бы увеличивать или уменьшать размер стека при необходимости.
Увеличивать или уменьшать массив каждый раз на единицу не эффективно с точки зрения времени выполнения. Так как постоянно придется переписывать все стек целиком. Поэтому лучше использовать метод «удвоения».
Таким образом при полном заполнении стека увеличиваем его длину в два раза. Т.е. выделяем память под массив в два раза больше текущего и переписываем туда содержимое стека. В результате копирование данных происходит не очень часто.
Уменьшаем же длину стека в том случае когда он остается заполненным на четверть. В этом случае выделяем под массив память в два раза меньше текущего размера и копируем туда содержимое.
Уменьшение размера при достижении 25%, а не половины делаем для того чтобы избежать «гонок» на граничных значения. Например, сделали push, а стек полон. В результате выделили память и произвели копирование всего стека. Потом сделали pop — в результате стек оказался заполнен наполовину — надо уменьшать размер, а значит опять выделять память и копировать данные.
Именно поэтому уменьшаем размер стека только тогда когда он заполнен на четверть.
В результате получаем оптимизированный алгоритм по использованию памяти и по времени выполнения.