数组中栈与队列的实现

前言

    数组是应用最广泛的数据存储结构。它被植入到大部分编程语言中。由于数组十分容易懂,所以它被用来作为介绍数据结构的起点非常合适。
下面来看一下栈和队列的在数组当中的实现:.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
// <- [] //遍历完成

结语

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