Основы программирования на JavaScript



              

Создание собственного стека


Чтобы создать свой собственный стек, необходимо удалить рекурсивную часть нашей функции. Мы все равно собираемся многократно вызывать функцию, но собираемся вызывать ее из другой функции, а не из себя самой.

var Stack = [];

function floodFill(x, y){ fillPixel(x, y);

while(Stack.length>0){ toFill = Stack.pop(); fillPixel(toFill[0], toFill[1]); } }

function fillPixel(x, y){ if(!alreadyFilled(x, y)) fill(x, y);

if(!alreadyFilled(x, y-1)) Stack.push([x, y-1]); if(!alreadyFilled(x+1, y )) Stack.push([x+1, y ]); if(!alreadyFilled(x, y+1)) Stack.push([x, y+1]); if(!alreadyFilled(x-1, y )) Stack.push([x-1, y ]); }

function fill(x, y){ // эта функция будет фактически изменять цвет поля }

function alreadyFilled(x, y){ // эта функция проверяет, что квадрат еще не был закрашен }

Как можно видеть, процесс не намного сложнее, но требует немного больше микроуправления, чем написанный ранее рекурсивный код. Вместо рекурсивного вызова функции floodFill создается переменная Stack, содержащая список квадратов, которые необходимо закрасить. Затем функция fillPixel заполняет этот массив, а функция floodFill извлекает последний элемент и закрашивает его. Когда все будет сделано, результат будет таким же, как и у первой функции, которая была написана, с одним исключением: эта функция не имеет никаких ограничений в отношении величины сетки.

Отметим, что существует очень немного рекурсивных функций, которые будут реально переполнять стек JavaScript. В действительности это не совсем верно. Почти любая рекурсивная функция может переполнить стек, но чаще всего данные, которые функция получает от пользователя, делают это крайне маловероятным событием. Когда, например, вы встретите документ XML с глубиной вложения узлов, равной 1000? Почти наверняка - никогда.




Содержание  Назад  Вперед