JS数据结构学习（一）

栈

是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

实现

声明栈的方法：

push():添加一个（或多个）新元素到栈顶。
pop():移除栈顶的元素，同时返回被移除的元素。
peek():返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
isEmpty():如果栈里没有任何元素就返回true，否则返回false。
clear():移除栈里的所有元素。
size():返回栈里的元素个数。这个方法和数组的length属性很类似。

function Stack() {
    var items = [];

    this.push = function(element) {
        items.push(element);
    };

    this.pop() = function() {
        return items.pop();
    };

    this.peek = function() {
        return items[items.length-1];
    };

    this.isEmpty = function() {
        return items.length === 0;
    };

    this.clear = function() {
        items = [];
    };

    this.size = function() {
        return items.length;
    }
}

队列

队列是遵循先进先出（FIFO）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

实现

声明队列的方法：

enqueue(element(s)):向队列尾部添加一个（或多个）新的项。
dequeue():移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
front():返回队列中第一个元素。队列不做任何变动。
isEmpty():如果队列中不包含任何元素，返回true，否则返回false。
clear():移除栈里的所有元素。
size():返回队列包含的元素个数，与数组的length属性类似。

function Queue() {
    var items = [];

    this.enqueue = function(element) {
        items.push(element);
    };

    this.dequeue = function() {
        return items.shift();
    };

    this.front = function() {
        return items[0];
    };

    this.isEmpty = function() {
        return items.length === 0;
    };

    this.clear = function() {
        items = [];
    };

    this.size = function() {
        return items.length;
    }
}

优先队列

队列实现的一个修改版，元素的添加和移除是基于优先级的。实现一个优先队列，有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级移除它们。

function PriorityQueue() {
    var items = [];

    function QueueElement(element, priority) {
        this.element = element;
        this.priority = priority;
    }

    this.enqueue = function(element, priority) {
        var queueElement = new QueueElement(element, priority);
        if(this.isEmpty()) {
            items.push(queueElement);
        } else {
            var added = false;
            for(var i=0;i<items.length;i++) {
                if(queueElement.priority < items[i].priority) {
                    items.splice(i, 0, queueElement);
                    added = true;
                    break;
                }
            }
            if(!added) {
                items.push(queueElement);
            }
        }
    }
}

循环队列–击鼓传花

还有另一个修改版的队列实现，就是循环队列。循环队列的一个例子就是击鼓传花游戏。在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩一个孩子（胜者）。

function hotPotato (nameList, num){
    var queue = new Queue(); // {1}
    for (var i=0; i<nameList.length; i++){
        queue.enqueue(nameList[i]); // {2}
    }
    var eliminated = '';
    while (queue.size() > 1){
        for (var i=0; i<num; i++){
            queue.enqueue(queue.dequeue()); // {3}
        }
        eliminated = queue.dequeue();// {4}
    console.log(eliminated + '在击鼓传花游戏中被淘汰。');
    }
    return queue.dequeue();// {5}
}
var names = ['John','Jack','Camila','Ingrid','Carl'];
var winner = hotPotato(names, 7);
console.log('胜利者：' + winner);

链表

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点开始迭代列表直到找到所需的元素。

Posted by Hexo on 2017-07-28