巧用javascript数组实现数据结构-堆栈与队列

巧用javascript数组实现数据结构-堆栈与队列

huangdijia 发表于 2011-7-23 分类 

前几天，有一位朋友问起我，Javascript如何实现堆栈和队列。我想了想，JavaScript里貌似只有数组，没有堆栈和队列这两种类型，于是我想是否可以利用JavaScript里的数组模拟实现这两种数据类型，答案是肯定的，因为在其他一些编程语言（如PHP）里也没有这两种类型，但它们同样是利用数组来实现。

简单的利用javascript的数组实现数据结构中的堆栈和队列。

Stack.js源码：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

/*  * @brief: 定义堆栈类  * @remark: 实现堆栈基本功能  */ function Stack(){     //存储元素数组     var aElement = new Array();     /*     * @brief: 元素入栈     * @param: 入栈元素列表     * @return: 堆栈元素个数     * @remark: 1.Push方法参数可以多个     *    2.参数为空时返回-1     */     Stack.prototype.Push = function(vElement){         if (arguments.length == 0)             return - 1;         //元素入栈         for (var i = 0; i < arguments.length; i++){             aElement.push(arguments[i]);         }         return aElement.length;     }     /*     * @brief: 元素出栈     * @return: vElement     * @remark: 当堆栈元素为空时,返回null     */     Stack.prototype.Pop = function(){         if (aElement.length == 0)             return null;         else             return aElement.pop();     }     /*     * @brief: 获取堆栈元素个数     * @return: 元素个数     */     Stack.prototype.GetSize = function(){         return aElement.length;     }     /*     * @brief: 返回栈顶元素值     * @return: vElement     * @remark: 若堆栈为空则返回null     */     Stack.prototype.GetTop = function(){         if (aElement.length == 0)             return null;         else             return aElement[aElement.length - 1];     }     /*     * @brief: 将堆栈置空     */     Stack.prototype.MakeEmpty = function(){         aElement.length = 0;     }     /*     * @brief: 判断堆栈是否为空     * @return: 堆栈为空返回true,否则返回false     */     Stack.prototype.IsEmpty = function(){         if (aElement.length == 0)             return true;         else             return false;     }     /*     * @brief: 将堆栈元素转化为字符串     * @return: 堆栈元素字符串     */     Stack.prototype.toString = function(){         var sResult = (aElement.reverse()).toString();         aElement.reverse()         return sResult;     } }

Queue.js源码：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

/*  * @brief: 定义队列类  * @remark:实现队列基本功能  */ function Queue(){     //存储元素数组     var aElement = new Array();     /*     * @brief: 元素入队     * @param: vElement元素列表     * @return: 返回当前队列元素个数     * @remark: 1.EnQueue方法参数可以多个     *    2.参数为空时返回-1     */     Queue.prototype.EnQueue = function(vElement){         if (arguments.length == 0)             return - 1;         //元素入队         for (var i = 0; i < arguments.length; i++){             aElement.push(arguments[i]);         }         return aElement.length;     }     /*     * @brief: 元素出队     * @return: vElement     * @remark: 当队列元素为空时,返回null     */     Queue.prototype.DeQueue = function(){         if (aElement.length == 0)             return null;         else             return aElement.shift();       }     /*     * @brief: 获取队列元素个数     * @return: 元素个数     */     Queue.prototype.GetSize = function(){         return aElement.length;     }     /*     * @brief: 返回队头素值     * @return: vElement     * @remark: 若队列为空则返回null     */     Queue.prototype.GetHead = function(){         if (aElement.length == 0)             return null;         else             return aElement[0];     }     /*     * @brief: 返回队尾素值     * @return: vElement     * @remark: 若队列为空则返回null     */     Queue.prototype.GetEnd = function(){         if (aElement.length == 0)             return null;         else             return aElement[aElement.length - 1];     }     /*     * @brief: 将队列置空     */     Queue.prototype.MakeEmpty = function(){         aElement.length = 0;     }     /*     * @brief: 判断队列是否为空     * @return: 队列为空返回true,否则返回false     */     Queue.prototype.IsEmpty = function(){         if (aElement.length == 0)             return true;         else             return false;     }     /*     * @brief: 将队列元素转化为字符串     * @return: 队列元素字符串     */     Queue.prototype.toString = function(){         var sResult = (aElement.reverse()).toString();         aElement.reverse()         return sResult;     } }

测试：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

var oStack = new Stack(); oStack.Push("abc", "123", 890); console.log(oStack.toString()); oStack.Push("qq"); console.log(oStack.toString()); //  alert(oStack.GetSize()); //  alert(oStack.Pop()); //  alert(oStack.GetTop()); //  oStack.MakeEmpty(); //  alert(oStack.GetSize()); //  alert(oStack.toString()); delete oStack; var oQueue = new Queue(); oQueue.EnQueue("bbs", "fans", "bruce"); console.log(oQueue.toString()); oQueue.EnQueue(23423); console.log(oQueue.toString()); //  alert(oQueue.DeQueue()); //  alert(oQueue.GetSize()); //  alert(oQueue.GetHead()); //  alert(oQueue.GetEnd()); //  oQueue.MakeEmpty(); //  alert(oQueue.IsEmpty()); //  alert(oQueue.toString()); delete oQueue;