数据结构的javascript实现

栈

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

function Stack() {

  var data = [];


  // 入栈：放在数组末尾
  this.push = function(ele) {
    data.push(ele);
  };

  // 出栈：弹出栈顶元素（数组末尾的元素）
  this.pop = function() {
    return data.pop();
  };

  // 查看栈顶元素
  this.peek = function() {
    return data[data.length - 1];
  }

  // 判断栈空：返回布尔
  this.isAmpty = function() {
    return data.length === 0
  };

  // 清空栈
  this.clear = function() {
    data = [];
  };

  // 返回栈的长度
  this.size = function() {
    return data.length;
  };


  // 以字符串显示栈中所有内容
  this.print = function() {
    console.log(data.toString());
  };
}

var s = new Stack;
s.push("a");
s.push("b");
s.push("c");
s.push("d");
s.push("e");

s.print();  // a,b,c,d,e

队列

function print(x) {
    console.log(x);
}

//////////////////////////////////

function Queue() {
    this.data = [];  // 队列用数组实现
    this.enqueue = enqueue;  // 入队
    this.dequeue = dequeue;  // 出队
    this.front = front;  // 求队头元素
    this.back = back;  // 求队尾元素
    this.toString = toString;
    this.empty = empty;  // 判断队空
}

// 入队
function enqueue(ele) {
    this.data.push(ele);
}

// 出队
function dequeue() {
    return this.data.shift();
}

// 求队头元素
function front() {
    return this.data[0];
}

// 求队尾元素
function back() {
    return this.data[this.data.length - 1];
}


function toString() {
    var retStr = "";
    for (var i = 0; i < this.data.length; ++i) {
        retStr += this.data[i] + "
";
    }
    return retStr;
}

// 判断队空
function empty() {
    if (this.data.length == 0) {
        return true;
    } else {
        return false;
    }
}

// 测试程序
var q = new Queue();
q.enqueue("Meredith");
q.enqueue("Cynthia");
q.enqueue("Jennifer");
print(q.toString());
// Meredith
// Cynthia
// Jennifer

q.dequeue();
print(q.toString());
// Cynthia
// Jennifer
print("Front of queue: " + q.front());
// Front of queue: Cynthia
print("Back of queue: " + q.back());
// Back of queue: Jennifer

单链表

function print(x) {
    console.log(x);
}

//////////////////////////////////
// 结点类
function Node(element) {
    this.element = element;
    this.next = null;
}

// 方法类
function LList() {
    this.head = new Node("head");
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
}

// 移除一个结点
function remove(item) {
    var prevNode = this.findPrevious(item);
    if (!(prevNode.next == null)) {
        prevNode.next = prevNode.next.next;
    }
}

// 找到当前结点的前一个结点
function findPrevious(item) {
    var currNode = this.head;
    while (!(currNode.next == null) &&
        (currNode.next.element != item)) {
        currNode = currNode.next;
    }
    return currNode;
}

// 展示所有结点
function display() {
    var currNode = this.head;
    while (!(currNode.next == null)) {
        print(currNode.next.element);
        currNode = currNode.next;
    }
}

// 查找指定结点
function find(item) {
    var currNode = this.head;
    while (currNode.element != item) {
        currNode = currNode.next;
    }
    return currNode;
}

// 在item后面插入newEle
function insert(newElement, item) {
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Carlisle", "Russellville");
cities.insert("Alma", "Carlisle");
cities.display();
// Conway
// Russellville
// Carlisle
// Alma
print('
')
cities.remove("Carlisle");
cities.display();
// Conway
// Russellville
// Alma

双向链表

// 结点类
function Node(element) {
    this.element = element;
    this.next = null;
    this.previous = null;
}
// 方法类
function LList() {
    this.head = new Node("head");
    this.find = find;  // 查找给定数据
    this.insert = insert;  // 在指定结点后面插入一个结点
    this.display = display;  // 展示链表
    this.remove = remove;  // 移除一个结点
    this.findLast = findLast;  // 找到最后一个结点
    this.dispReverse = dispReverse;  // 反序展示双向链表
}

// 反序展示链表
function dispReverse() {
    var currNode = this.head;
    currNode = this.findLast();
    while (!(currNode.previous == null)) {
        print(currNode.element);
        currNode = currNode.previous;
    }
}

// 找到最后一个结点
function findLast() {
    var currNode = this.head;
    while (!(currNode.next == null)) {
        currNode = currNode.next;
    }
    return currNode;
}

// 移除一个结点
function remove(item) {
    var currNode = this.find(item);
    if (!(currNode.next == null)) {
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    }
}

// 展示链表
function display() {
    var currNode = this.head;
    while (!(currNode.next == null)) {
        print(currNode.next.element);
        currNode = currNode.next;
    }
}

// 找到指定结点
function find(item) {
    var currNode = this.head;
    while (currNode.element != item) {
        currNode = currNode.next;
    }
    return currNode;
}

// 把新结点插入到指定结点后面
function insert(newElement, item) {
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    newNode.previous = current;
    current.next = newNode;
}

var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Carlisle", "Russellville");
cities.insert("Alma", "Carlisle");
cities.display();
print('
');
cities.remove("Carlisle");
cities.display();
print('
');
cities.dispReverse();

打印结果：

二叉树(暂未调试)

// *模拟输出
function print(x) {
    console.log(x);
}


function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}

function show() {
    return this.data;
}

function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
}

function insert(data) {
    var n = new Node(data, null, null);
    if (this.root == null) {
        this.root = n;
    } else {
        var current = this.root;
        var parent;
        while (true) {
            parent = current;
            if (data < current.data) {
                current = current.left;
                if (current == null) {
                    parent.left = n;
                    break;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = n;
                    break;
                }
            }
        }
    }
}

function inOrder(node) {
    if (!(node == null)) {
        inOrder(node.left);
        putstr(node.show() + " ");
        inOrder(node.right);
    }
}


function preOrder(node) {
    if (!(node == null)) {
        putstr(node.show() + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}


function postOrder(node) {
    if (!(node == null)) {
        postOrder(node.left);
        postOrder(node.right);
        putstr(node.show() + " ");
    }
}


function getMin() {
    var current = this.root;
    while (!(current.left == null)) {
        current = current.left;
    }
    return current.data;
}

function getMax() {
    var current = this.root;
    while (!(current.right == null)) {
        current = current.right;
    }
    return current.data;
}

function find(data) {
    var current = this.root;
    while (current != null) {
        if (current.data == data) {
            return current;
        } else if (data < current.data) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return null;
}

function remove(data) {
    root = removeNode(this.root, data);
}

function removeNode(node, data) {
    if (node == null) {
        return null;
    }
    if (data == node.data) {
        // 没有子节点的节点
        if (node.left == null && node.right == null) {
            return null;
        }
        // 没有左子节点的节点
        if (node.left == null) {
            return node.right;
        }
        // 没有右子节点的节点
        if (node.right == null) {
            return node.left;
        }
        // 有两个子节点的节点
        var tempNode = getSmallest(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
    } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
    } else {
        node.right = removeNode(node.right, data);
        return node;
    }
}