数组中栈与队列的实现

Posted on   |   In   |     |  

前言

    数组是应用最广泛的数据存储结构。它被植入到大部分编程语言中。由于数组十分容易懂，所以它被用来作为介绍数据结构的起点非常合适。
下面来看一下栈和队列的在数组当中的实现：.pop, .push, .shift和 .unshift

先来看栈的实现

每个人都知道.push可以再数组末尾添加元素，但是你知道可以使用[].push(‘a’, ‘b’, ‘c’, ‘d’, ‘z’)一次性添加多个元素吗？

.pop 方法是.push 的反操作，它返回被删除的数组末尾元素。如果数组为空，将返回void 0 即是(undefined),使用.pop和.push可以创建LIFO (last in first out)栈。

(last in first out)栈的特性是后进先出，正向前面的last in first out的翻译
push()从尾部添加,返回添加后数组的长度
pop()从尾部删除,返回被删除的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
function Stack () { //声明一个Stack构造函数
    this._stack = [];  //在其实例对象上动态添加一个_stack = [],方便下面借用其方法，一般`_`表示私有
}
Stack.prototype.next = function () { //再其原型属性添加一个next方法，其实就是借用了数组的pop方法；
    return this._stack.pop(); 
}
Stack.prototype.add = function () { //下面的实现其实·就是借用了数组的push方法
    return this._stack.push.apply(this._stack, arguments); //这里使用了apply借用上下文模式，主要是想利用它第二个参数是数组的作用，虽然arguments是伪数组，也可以实现让其里面的参数逐个的添加到this._stack中，这种借用上下文调用的小技巧用的地方还是挺多的
}
stack = new Stack(); //实例化一个栈对象stack
stack.add(1,2,3); //从后面依次添加3个元素
stack.next(); //弹出最后一个元素，
// <- 3

接下来是队列的实现

使用.shift和 .unshift即可创建FIFO (first in first out)队列。

(first in first out)栈的特性是先进先出，正向前面的first in first out的翻译
unshift()从头部添加,返回添加后数组的长度
shift()从头部删除,返回被删除的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
function Queue () { //声明一个Queue构造函数
    this._queue = []; //同样在实例对象自定义一个_queue私有属性方便下面借用其方法，一般`_`表示私有
}
Queue.prototype.next = function () { //再其原型属性添加一个next方法，其实就是借用了数组的shift方法，也就是从前面删除元素
    return this._queue.shift();
}
Queue.prototype.add = function () { //借用其unshift方法，也就是从前面添加元素
    return this._queue.unshift.apply(this._queue, arguments);
}
queue = new Queue();//实例化一个队列对象queue；
queue.add(1,2,3); //从前面依次添加三个元素
queue.next(); //弹出第一个元素
// <- 1

//使用shift或者pop能够很方便的遍历一个数组元素
list = [1,2,3,4,5,6,7,8,9,10]
while (item = list.shift()) {
console.log(item)
}
list
// <- [] //遍历完成

结语

    栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。栈的使用遍布程序语言实现的方方面面，从表达式求值到处理函数调用；栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子，盘子洗净后，也只能摞在这一摞盘子的最上面。结合前面的比喻，再记住后进先出对队列的理解就差不多了；
    队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出，这点和栈不一样，在栈中，最后入栈的元素反而被优先处理。可以将队列想象成在银行前排队的人群，排在最前面的人第一个办理业务，新来的人只能在后面排队，直到轮到他们为止。队列被用在很多地方，比如提交操作系统执行的一系列进程、打印任务池等，一些仿真系统用队列来模拟银行或杂货店里排队的顾客；结合前面的比喻，再记住先进先出对队列的理解就差不多了；