其实JS很“流氓的”,JS的数组完全既可以是队列也可以是栈。
因为数组的push,pop就是栈的一组方法嘛。数据的push,shift就是队列的一组方法嘛。但是数据结构知识的需要,数据结构中对队列、栈的定义很明确:栈,先进后出
队列,先进先出
现在要用两个栈实现一个队列,那么首先定义一个栈构造函数吧。
定义一个栈Stack构造函数
new两个Stack,stack1,stack2
stack1实现队列的进就好了
stack2实现队列的出就好了
重点来了,进的时候去的是stack1,怎么从stack2出数据呢当栈2为空,栈1不为空时,把栈1的数据依次pop出去到栈2中,这样再栈2pop时就是队列应该pop的数据了
上代码:
function Queue(){ var items = []; function Stack() { var item = []; this.push = function (elem) { item.push(elem); return item; }; this.pop = function () { return item.pop(); }; this.isEmpty = function () { return item.length === 0; }; this.get = function () { return item; }; } var stack1 = new Stack(); var stack2 = new Stack(); this.push = function (elem) { stack1.push(elem); return items.push(elem); } this.pop = function () { if(stack1.isEmpty() && stack2.isEmpty()){ throw new Error("空队列"); } if(stack2.isEmpty() && !stack1.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } return stack2.pop(); } }; this.get = function () { if(!stack2.isEmpty()){ return stack2.get().reverse(); }else{ return items; } }}var queue = new Queue();queue.push(0);queue.push(1);queue.push(2);queue.get();queue.pop();queue.get();