数据结构之栈和队列
数据结构有许多种，上篇文章分享的是可以存储简单数据的列表，例如待办事项，购物清单等。今天要跟大家分享的是两种非常常见的也必须了解的数据结构——栈与队列。
栈的定义
什么是栈呢？它是一种“后入先出”的数据结构，它跟列表一样，都是可以用来存储数据，但是却要比列表严格的多，栈的数据只能在栈顶添加或删除。举个例子，在麦当劳用餐时的那些盘子，捡餐员在拿盘子时，总是从一摞盘子的最上端拿（栈顶），然后放上食品在端给客人，而那些擦餐盘的人，也总是在最上面拿起餐盘擦拭后不断地叠放成一摞餐盘，这里的餐盘就可看成是栈，数据的添加或删除总是在最上端进行。下图展示了栈的构成以及简单的入栈与出栈过程。
图片来自网络
栈的主要操作方法
栈的常用操作就是入栈和出栈，入栈用的是 push() 方法，出栈用的是 pop() 方法，还有一个方法是 peek() ，该方法可以返回栈顶的元素而不删除它，相应的 pop() 方法虽然也可以得到栈顶的元素，但会将它删除。
栈的实现
在 JavaScript 中，通常使用数组来实现栈。下面我们定义一个名为 Stack 的构造函数用来表示栈。
function Stack() {
this.dataStore = [];
this,top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
}
dataStore 是一个数组，用来存储栈中的元素，而变量 top 记录栈顶的位置，初始位置为 0，push 、pop 和 peek 分别对应三个方法，下面来实现这些方法。
首先是 push() ,入栈。
function push() {
this.dataStore[this.top++] = element;
}
这里 top++ 很有意思，要知道 + 号在变量后和变量前是不同的，这里的逻辑是，当元素入栈后，变量 top 的值就对应当前入栈元素的位置，然后 top++ ，自增后的值就是下一个元素入栈时的位置了。
接下来是出栈方法 pop() 。
function pop() {
return this.dataStore[--this.top];
}
前面说了，栈只能在最顶端添加、删除数据，所以我们必须要知道栈顶现在存放的是哪个数值才能将它删除，于是我们使用 top 来标记它的位置，现在出栈，只需要把指向栈顶的位置的节点数据拿掉就行了。
最后一个方法是取栈顶元素的 peek() 方法,相信也不难理解，就把栈顶元素直接返回就行，注意栈顶元素的位置是第 top - 1 个位置。
function peek() {
return this.dataStore[this.top - 1];
}
除了上述的基本操作方法外，还有其它方法可以有作用。来看下面这两个方法
function length() {
return this.top;
}
function clear() {
this.top = 0;
}
上面的方法一个是可以获取栈内存储了多少个元素的 length() 方法， 另一个是 clear() ,听名字就知道是把一个栈清空，通过将 top 的值归零。
栈的完整代码
栈的完整代码以及测试如下
function Stack() {
this.dataStore = [];
this,top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.length = length;
this.clear = clear;
}
function push() {
this.dataStore[this.top++] = element;
}
function pop() {
return this.dataStore[--this.top];
}
function peek() {
return this.dataStore[this.top - 1];
}
function length() {
return this.top;
}
function clear() {
this.top = 0;
}
var s = new Stack();
s.push("xiaoming");
s.push("xiaohong");
s.push("Mike");
console.log("栈的长度为： "+s.length());
console.log(s.peek());
s.clear();
console.log("当前长度为： "+s.length());
运行结果为：
栈的长度为： 3
Mike
当前长度为： 0
队列的定义
队列是一种与栈截然不同的数据结构，栈的特点是后入先出，最后入栈的元素会优先处理而弹出，而队列的特点则是先入先出，最先进栈的也会最终先出栈，这有点类似于银行窗口前排队办业务的人群，排在最前面的先办理业务，后面来的就依次排队。
队列的主要操作方法
与栈一样，队列也是用数组来实现，它的主要操作方法同样是入队（enqueue）,出队（dequeue）和读取队头的元素（peek）,读取队头元素同样不会删除元素，只返回。此外还有清空队列元素（clear）和获取队列元素个数（length）。
队列的实现
首先定义一个 Queue 类用来表示队列。
function Queue() {
this.dataStore = []; // 存储队列元素
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
}
接下来实现入队方法 enqueue() ：
function enqueue(element) {
this.dataStore.push(element);
}
可以看到，用数组来实现队列非常简单，入队只需一个 push() 方法即可向队尾添加元素。
function dequeue() {
return this.dataStore.shift();
}
shift 是数组的一个操作方法，可以将数组的第一个元素删除。
function front() {
return this,dataStore[0];
}
function back() {
return this.dataStore[this.dataStore.length - 1];
}
这两个分别是读取队列的第一个元素和最后一个元素，很简单，直接返回数组的第一个元素和最后一个元素即可。
function toString() {
var str = "";
for (var i = 0; i < this.dataStore.length; i++) {
str += this.dataStore[i] + "\n";
}
return str;
}
这个方法显示队列元素，类似控制台 console 输出元素。
function empty() {
if (this.dataStore.length == 0) {
return true;
}
else {
return false;
}
}
这是一个判空方法，每次使用队列前要判断是否为空才可进行下一步的操作。
队列完整代码及测试
function Queue() {
this.dataStore = []; // 存储队列元素
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
}
function enqueue(element) {
this.dataStore.push(element);
}
function dequeue() {
return this.dataStore.shift();
}
function front() {
return this,dataStore[0];
}
function back() {
return this.dataStore[this.dataStore.length - 1];
}
function toString() {
var str = "";
for (var i = 0; i < this.dataStore.length; i++) {
str += this.dataStore[i] + "\n";
}
return str;
}
function empty() {
if (this.dataStore.length == 0) {
return true;
}
else {
return false;
}
}
var q = new Queue();
q.enqueue("Mike");
q.enqueue("Hello");
q.enqueue("hhhh");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("队列的第一个元素是: " + q.front());
console.log("队列的最后一个元素是: " + q.back());
运行结果如下：
Mike
Hello
hhhh
Hello
hhhh
队列的第一个元素是: Hello
队列的最后一个元素是: hhhh
