一、栈结构


1、封装栈结构及方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function Stack() {
//栈属性
this.items = [];

// 入栈
Stack.prototype.push = function(element) {}

// 出栈
Stack.prototype.pop = function() {}

// 查看栈顶元素
Stack.prototype.peek = function() {}

// 判断栈是否为空
Stack.prototype.isEmty = function() {}

// 查看栈长度
Stack.prototype.size = function() {}

// toString 方法
Stack.prototype.toString = function() {}
}

2、具体方法实现

  • 入栈
1
2
3
4
Stack.prototype.push = function(element) {
// 在数组的尾部压入元素
return this.items.push(element);
}
  • 出栈
1
2
3
4
Stack.prototype.pop = function() {
// 从数组尾部删除元素,并返回栈顶元素
return this.items.pop();
}
  • 查看栈顶元素
1
2
3
4
Stack.prototype.peek = function() {
// 从数组尾部查看元素
return this.items[this.items.length - 1];
}
  • 判断栈是否为空
1
2
3
4
Stack.prototype.isEmty = function() {
// 判断数组是否为空
return this.items.length === 0;
}
  • 查看栈长度
1
2
3
4
Stack.prototype.size = function() {
// 查看数组长度
return this.items.length;
}
  • toString 方法
1
2
3
4
5
6
7
8
Stack.prototype.toString = function() {
let resultString = '';
// 遍历数组
for (let i = 0; i < this.items.length; i++) {
resultString += this.items[i] + ''
}
return resultString
}


二、队列结构


1、封装队列结构及方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 队列封装
function Queue() {
// 属性
this.items = [];

// 入队
Queue.prototype.enqueue = function(element) {}

// 出队
Queue.prototype.inqueue = function() {}

// 查看队头元素
Queue.prototype.front = function() {}

// 判断队列是否为空
Queue.prototype.isEmpty = function() {}

//查看队列长度
Queue.prototype.size = function() {}

// toString 方法
Queue.prototype.toString = function() {}
}

2、 具体方法实现

  • 入队
1
2
3
4
Queue.prototype.enqueue = function(element) {
// 在数组的尾部添加元素
return this.items.push(element);
}
  • 出队

    1
    2
    3
    4
    Queue.prototype.inqueue = function() {
    // 从数组中删除队头元素,并返回队头元素
    return this.items.shift();
    }
  • 查看队头元素

    1
    2
    3
    4
    Queue.prototype.front = function() {
    // 从数组中查看数组第一个元素
    return this.items[0];
    }
  • 判断队列是否为空

    1
    2
    3
    4
    Queue.prototype.isEmpty = function() {
    // 判断数组是否为空
    return this.items.length === 0;
    }
  • 查看队列长度

    1
    2
    3
    4
    Queue.prototype.size = function() {
    // 查看数组长度
    return this.items.length;
    }
  • toString 方法

    1
    2
    3
    4
    5
    6
    7
    8
    Queue.prototype.toString = function() {
    let resultString = '';
    // 遍历数组
    for (let i = 0; i < this.items.length; i++) {
    resultString += this.items[i] + ''
    }
    return resultString
    }


三、优先级队列结构


1、 封装优先级队列结构及方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function PriorityQueue() {

// 元素包含两部分 element 数据 priority 优先级
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}

// 封装属性
this.items = [];

// 实现插入方法
PriorityQueue.prototype.enqueue = function(element, priority){}

// 其他方法跟队列的一致
}

2、具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
PriorityQueue.prototype.enqueue = function(element, priority) {
// 创建 QueueElement 对象
const queueElement = new queueElement(element, priority)

// 判断队列是否为空
if (this.items.length == 0) {
// 为空 直接将数据插入到数组中
this.items.push(queueElement)
} else {
let added = false;
for (let i = 0; i < this.items.length; i++) {
// 数字越小,优先级越高。
if(queueElement.priority < this.items[i].priority) {
// 在数组的第 i 位插入数据
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}

if(!added) {
// 优先级在数组中最低直接插入
this.items.push(queueElement)
}
}
}

3、 其他方法跟队列一致



三、链表结构


1、封装链表结构及方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function LinkedList() {
//内部类: 节点类
function Node(data){
this.data = data;
this.next = null;
}

//属性
this.head = null;
this.length = 0;

// 向列表添加一个新的项
LinkedList.prototype.append = function(data) {}

// 向列表的特定位置插入一个新的项
LinkedList.prototype.insert = function(position, data) {}

// 获取对应位置的元素
LinkedList.prototype.get = function(position) {}

// 返回元素在列表中的索引,如果列表中没有该元素则返回 -1
LinkedList.prototype.indexOf = function(data) {}

// 修改某个位置的元素
LinkedList.prototype.update = function(position, newData) {}

// 从列表的特定位置移除一项
LinkedList.prototype.removeAt = function(position) {}

// 从列表中移除一项
LinkedList.prototype.remove = function(data) {}

// 如果链表中不包含任何元素,返回 true
LinkedList.prototype.isEmpty = function() {}

// 返回链表包含的元素个数
LinkedList.prototype.size = function() {}

// toString 方法
LinkedList.prototype.toString = function() {}

2、具体方法实现

  • 向列表添加一个新的项
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LinkedList.prototype.append = function(data) {
const newNode = new Node(data);
// 判断是否为第一个节点
if (this.length == 0) {
// 将头部指向第一结点
this.head = newNode;
} else {
// 在链表中找到最后一个结点插入节点
let current = this.head
while (current.next) { // 下一个结点不为空
current = current.next
}
// 最后节点的 next 指向新的节点
current.next = newNode;
}
// 更新链表长度
this.length += 1;
}
  • 向列表的特定位置插入一个新的项

在这里插入图片描述

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
LinkedList.prototype.insert = function(position, data) {
// 对 position 进行越界判断
if (position < 0 || position > this.length) return false;

// 创建 newNode
const newNode = new Node(data);

// 判断插入的位置是否是第一个位置
if (position == 0) {
newNode.next = head;
this.head = newNode;
} else {
// 找到指定位置
let index = 0;
let current = this.head;
// 前一个节点
let previous = null;
while (index++ < position) {
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
}
// 更新长度
this.length += 1
return true;
}
  • 获取对应位置的元素
1
2
3
4
5
6
7
8
9
10
LinkedList.prototype.get = function(position) {
// 对 position 进行越界判断
if (position < 0 || position >= this.length) return null;
let current = this.head
let index = 0;
while (index++ < position) {
current = current.next;
}
return current.data;
}
  • 返回元素在列表中的索引,如果列表中没有该元素则返回 -1
1
2
3
4
5
6
7
8
9
10
11
12
LinkedList.prototype.indexOf = function(data) {
let current = this.head;
let index = 0;
while(current) {
if (current.data === data) {
return index;
}
index += 1;
current = current.next;
}
return -1;
}
  • 修改某个位置的元素
1
2
3
4
5
6
7
8
9
10
LinkedList.prototype.update = function(position, newData) {
// 对 position 进行越界判断
if (position < 0 || position >= this.length) return false;
let current = this.head;
let index = 0;
while (index++ < position) {
current = current.next;
}
current.data = newData;
return true;
  • 从列表的特定位置移除一项

在这里插入图片描述


在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
LinkedList.prototype.removeAt = function(position) {
// 对 position 进行越界判断
if (position < 0 || position >= this.length) return null;
let current = this.head;

// 判断是否删除第一个节点
if (position === 0) {
this.head = this.head.next;
} else {
let index = 0;
let previous = null;
while (index++ < position) {
previous = current;
current = current.next;
}
// 前者指向后者的后者
previous.next = current.next;

// 更新长度
this.length -= 1;

return current.data;
}
  • 其他方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 从列表中移除一项
LinkedList.prototype.remove = function(data) {
// 根据 data 获取位置
let position = this.indexOf(data);
//根据位置信息,删除节点
return this.removeAt(position);
}

// 如果链表中不包含任何元素,返回 true
LinkedList.prototype.isEmpty = function() {
return this.length === 0;
}

// 返回链表包含的元素个数
LinkedList.prototype.size = function() {
return this.length;
}

// toString 方法
LinkedList.prototype.toString = function() {
let listString = '';
let current = this.head;

//循环获取节点
while (current) {
listString += current.data + " ";
current = current.next;
}
return listString;
}


四、双向链表结构


1、封装链表结构及其方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
function DoublyLinkedList() {
// 属性
this.head = null;
this.tail = null;
this.length = 0;

//内部类
function Node(data) {
this.data = data;
this.prev = null;
this.next = null;
}

// 向双向链表添加一个新的项
DoublyLinkedList.prototype.append = function(data) {}

// 向双向链表的特定位置插入一个新的项
DoublyLinkedList.prototype.insert = function(position, data) {}

// 获取对应位置的元素
DoublyLinkedList.prototype.get = function() {}

// 返回元素在列表中的索引,如果列表中没有该元素则返回 -1
DoublyLinkedList.prototype.indexOf = function(data) {}

// 修改某个位置的元素
DoublyLinkedList.prototype.update = function(position, newData) {}

// 从双向链表的特定位置移除一项
DoublyLinkedList.prototype.removeAt = function(position) {}

// 从双向链表移除一项
DoublyLinkedList.prototype.remove = function(data) {}

// 如果双向链表中不包含任何元素,返回 true
DoublyLinkedList.prototype.isEmpty = function() {}

// 返回双向链表包含的元素个数
DoublyLinkedList.prototype.size = function() {}

// 获取双向链表的第一个元素
DoublyLinkedList.prototype.getHead = function() {}

// 获取双向链表的最后一个元素
DoublyLinkedList.prototype.getTail = function() {}

// toString 方法
DoublyLinkedList.prototype.toString = function() {}

// 返回正向遍历的节点字符串形式
DoublyLinkedList.prototype.forwordString = function() {}

// 返回反向遍历的节点字符串形式
DoublyLinkedList.prototype.backwordString = function() {}
}

2、具体方法实现

  • 向双向链表添加一个新的项

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
DoublyLinkedList.prototype.append = function(data) {
const newNode = new Node(data);

// 判断是否添加的是第一个结点
if (this.length === 0) {
this.head = newNode;
} else {
// 找到链表的最后一个结点
let current = this.head;
while (current.next) {
current = current.next;
}
// 最后一个结点指向下一个结点
current.next = newNode;
// 新的结点指向上一个结点
newNode.prev = current;
}
// 更新指向最后一个结点
this.tail = newNode;
// 更新长度
this.length += 1;
}
  • 向双向链表的特定位置插入一个新的项

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
DoublyLinkedList.prototype.insert = function(position, data) {
// 越界判断
if (position < 0 || position > this.length) return false;

// 判断原来链表是否为空
if (this.length == 0) {
this.head = newNode;
this.tail = newNode;
} else {
// 判断 position 是否为 0
if (position == 0) {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
} else if (position == this.length) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
let current = this.head;
let index = 0;
while (index++ < position) {
current = current.next;
}
newNode.next = current;
newNode.prev = current.prev;
current.prev.next = newNode;
current.prev = newNode;
}
this.length += 1;
return true;
}
}
  • 获取对应位置的元素
1
2
3
4
5
6
7
8
9
10
DoublyLinkedList.prototype.get = function() {
// 越界判断
if (position < 0 || position >= this.length) return false;
let current = this.head;
let index = 0;
while (index++ < position) {
current = current.next;
}
return current.data;
}
  • 返回元素在列表中的索引,如果列表中没有该元素则返回 -1
1
2
3
4
5
6
7
8
9
10
11
12
DoublyLinkedList.prototype.indexOf = function(data) {
let current = this.head;
let index = 0;
while (current) {
if (current.data == data) {
return index;
}
current = current.next;
index += 1;
}
return -1;
}
  • 修改某个位置的元素
1
2
3
4
5
6
7
8
9
10
11
DoublyLinkedList.prototype.update = function(position, newData) {
// 越界判断
if (position < 0 || position >= this.length) return false;
let current = this.head;
let index = 0;
while (index++ < position) {
current = current.next;
}
current.data = newData;
return true;
}
  • 返回正反向遍历的节点字符串形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 返回正向遍历的节点字符串形式
DoublyLinkedList.prototype.forwordString = function() {
let current = this.head;
let resultString = "";
while (current) {
resultString += current.data + " ";
current = current.next;
}
return resultString;
}

// 返回反向遍历的节点字符串形式
DoublyLinkedList.prototype.backwordString = function() {
let current = this.tail;
let resultString = "";
while (current) {
resultString += current.data + " ";
current = current.prev;
}
return resultString;
}
// toString 方法
DoublyLinkedList.prototype.toString = function() {
this.forwordString();
}
  • 从双向链表的特定位置移除一项

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
DoublyLinkedList.prototype.removeAt = function(position) {
// 越界判断
if (position < 0 || position >= this.length) return null;
let current = this.head;
if (this.length == 1) {
// 只存在一个结点
this.head = null;
this.tail = null;
} else {
// postion 为 0
if (position == 0) {
this.head.next.prev = null;
this.head = this.head.next;
} else if (position == this.length - 1) {
// postion 为 this.length
current = this.tail;
this.tail.prev.next = null;
this.tail = this.tail.prev;
} else {
// postion 为 任意值
let index = 0;
while (index++ < position) {
current = current.next;
}
current.prev.next = current.next;
current.next.prev = current.prev;
}
}
this.length -= 1;
return current.data;
}

  • 其他方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 从列表移除一项
DoublyLinkedList.prototype.remove = function(data) {
let postion = this.indexOf(data);
return this.removeAt(postion);
}

// 如果链表中不包含任何元素,返回 true
DoublyLinkedList.prototype.isEmpty = function() {
return this.length == 0;
}

// 返回链表包含的元素个数
DoublyLinkedList.prototype.size = function() {
return this.length;
}

// 获取链表的第一个元素
DoublyLinkedList.prototype.getHead = function() {
return this.head.data;
}

// 获取链表的最后一个元素
DoublyLinkedList.prototype.getTail = function() {
return this.tail.data;
}

源码下载