栈
栈（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] + "\n";
}
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
// Jenniferq.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('\n')
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('\n');
cities.remove("Carlisle");
cities.display();
print('\n');
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;
}
}
