封装数据结构-1

2022/12/17 数据结构数据结构封装

# 一、栈结构


1、封装栈结构及方法
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() {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2、具体方法实现

  • 入栈
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;
	}
1
2
3
4
  • toString 方法
Stack.prototype.toString = function() {
		let resultString = '';
		// 遍历数组
		for (let i = 0; i < this.items.length; i++) {
			resultString += this.items[i] + ''
		}
		return resultString
	}
1
2
3
4
5
6
7
8


# 二、队列结构


1、封装队列结构及方法

// 队列封装
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() {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2、 具体方法实现

  • 入队
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;
	}
1
2
3
4
  • toString 方法
Queue.prototype.toString = function() {
		let resultString = '';
		// 遍历数组
		for (let i = 0; i < this.items.length; i++) {
			resultString += this.items[i] + ''
		}
		return resultString
	}
1
2
3
4
5
6
7
8


# 三、优先级队列结构


1、 封装优先级队列结构及方法
function PriorityQueue() {
	
	// 元素包含两部分 element 数据 priority 优先级
	function QueueElement(element, priority) {
		this.element = element;
		this.priority = priority;
	}
	
	// 封装属性
	this.items = [];
	
	// 实现插入方法
	PriorityQueue.prototype.enqueue = function(element, priority){}
	
	// 其他方法跟队列的一致
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2、具体实现

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)
		}
	}
}
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

3、 其他方法跟队列一致



# 三、链表结构


1、封装链表结构及方法
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() {}
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

2、具体方法实现

  • 向列表添加一个新的项
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
  • 向列表的特定位置插入一个新的项
    在这里插入图片描述
    在这里插入图片描述
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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
  • 获取对应位置的元素
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
2
3
4
5
6
7
8
9
10
  • 返回元素在列表中的索引,如果列表中没有该元素则返回 -1
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
11
12
  • 修改某个位置的元素
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
  • 从列表的特定位置移除一项

在这里插入图片描述
在这里插入图片描述

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
  • 其他方法
// 从列表中移除一项
	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
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


# 四、双向链表结构


1、封装链表结构及其方法
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() {}
}

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

2、具体方法实现

  • 向双向链表添加一个新的项
    在这里插入图片描述
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
  • 向双向链表的特定位置插入一个新的项
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
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
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.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
2
3
4
5
6
7
8
9
10
  • 返回元素在列表中的索引,如果列表中没有该元素则返回 -1
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
12
  • 修改某个位置的元素
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
  • 返回正反向遍历的节点字符串形式
// 返回正向遍历的节点字符串形式
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
  • 从双向链表的特定位置移除一项
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
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
26
27
28
29
30
31
32
  • 其他方法
// 从列表移除一项
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;
}
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

源码下载 (opens new window)