数据结构之栈和队列

数据结构有许多种，上篇文章分享的是可以存储简单数据的列表，例如待办事项，购物清单等。今天要跟大家分享的是两种非常常见的也必须了解的数据结构——栈与队列。

栈的定义

什么是栈呢？它是一种“后入先出”的数据结构，它跟列表一样，都是可以用来存储数据，但是却要比列表严格的多，栈的数据只能在栈顶添加或删除。举个例子，在麦当劳用餐时的那些盘子，捡餐员在拿盘子时，总是从一摞盘子的最上端拿（栈顶），然后放上食品在端给客人，而那些擦餐盘的人，也总是在最上面拿起餐盘擦拭后不断地叠放成一摞餐盘，这里的餐盘就可看成是栈，数据的添加或删除总是在最上端进行。下图展示了栈的构成以及简单的入栈与出栈过程。

图片来自网络

栈的主要操作方法

栈的常用操作就是入栈和出栈，入栈用的是 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

以上，对数据结构中栈和队列的简单介绍，想看关于栈和队列的更多实例代码，戳这里 栈与队列实例代码