JavaScript数据结构与算法——什么是栈

之前说到数组操作的时候有提到push()方法和pop()方法，他们分别可以往一个数组最后推送一个元素或者移除一个元素。而这两个方法其实就是对栈操作的两种主要操作

栈是一种常见的线性数据结构，栈内的元素只能从一端访问，如下图所示，进栈和出栈都是从一端进行，这一端叫做栈顶。

因为栈结构只有一端能访问，所以你只能操作离栈顶最近的那个元素，这种数据结构被称为后入先出（LIFO）。

下图演示了使用push()方法和pop()方法操作栈的过程。

push()方法表示进栈，pop()方法表示出栈。

实现一个栈

来简单实现一个栈吧

function Stack() {
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
}

定义一个构造函数，然后其中初始化一个空数组，top表示栈顶元素的位置，当有元素进入栈时就会代替top的位置，然后top加一。

声明一个实例，下面都用这个实例来演示：

var stack = new Stack()

然后实现一些方法：

实现push方法

function push(element) {
    this.dataStore[this.top++] = element;
}

实现一个push方法用来往栈中加入元素，并将其储存在当前的top值的位置，然后再给top+1。

stack.push("good man")
stack.top       // 1

实现pop方法

function pop() {
    return this.dataStore[--this.top];
}

实现pop方法来给top值-1，即移除栈顶元素并返回移除的这个值

看这个例子：

stack.pop()     // "good man"
stack.top       // 0

实现peek方法

function peek() {
    return this.dataStore[this.top-1];
}

peek()方法用来返回栈顶元素，即栈的第top-1个元素，

stack.peek()    // undefined

因为现在stack是空的，没有元素，所有会返回undefined。

实现clear方法

可以设置一个clear方法来把top设置为0，即清空栈内所有的元素。

function clear() {
    this.top = 0;
}

使用栈

栈的用处很多，这里写一个例子，判断一个字符串是否回文，我前两天有用c写了一个，下面用上面实现的那个栈来实现一遍。

function isPalindrome(word) {
    var s = new Stack();
    for (var i = 0; i < word.length; ++i) {
        s.push(word[i]);
    }
    var rword = "";
    while (s.top > 0) {
        rword += s.pop();
    }
    if (word == rword) {
        return (word + " is a palindrome.");
    }
    else {
        return (word + " is not a palindrome.");
    }
}

非常简单，只要把这个字符串依次放入一个栈中，再依次拿出来，按照栈的LIFO特性，拿出来的这个字符串就会是之前反转的字符串了，再一比较，完事。

> isPalindrome("mmm")
< "mmm is a palindrome."
> isPalindrome("good")
< "good is not a palindrome."