封装数据结构-1

一、栈结构

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

2、具体方法实现

• 入栈

Stack.prototype.push = function(element) {
		// 在数组的尾部压入元素
		return this.items.push(element);
	}

• 出栈

Stack.prototype.pop = function() {
		// 从数组尾部删除元素，并返回栈顶元素
		return this.items.pop();
	}

• 查看栈顶元素

Stack.prototype.peek = function() {
		// 从数组尾部查看元素
		return this.items[this.items.length - 1];
	}

• 判断栈是否为空

Stack.prototype.isEmty = function() {
		// 判断数组是否为空
		return this.items.length === 0;
	}

• 查看栈长度

Stack.prototype.size = function() {
		// 查看数组长度
		return this.items.length;
	}

• toString 方法

Stack.prototype.toString = function() {
		let resultString = '';
		// 遍历数组
		for (let i = 0; i < this.items.length; i++) {
			resultString += this.items[i] + ''
		}
		return resultString
	}

---

二、队列结构

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

2、 具体方法实现

• 入队

Queue.prototype.enqueue = function(element) {
		// 在数组的尾部添加元素
		return this.items.push(element);
	}

• 出队

Queue.prototype.inqueue = function() {
		// 从数组中删除队头元素，并返回队头元素
		return this.items.shift();
	}

• 查看队头元素

Queue.prototype.front = function() {
		// 从数组中查看数组第一个元素
		return this.items[0];
	}

• 判断队列是否为空

Queue.prototype.isEmpty = function() {
		// 判断数组是否为空
		return this.items.length === 0;
	}

• 查看队列长度

Queue.prototype.size = function() {
		// 查看数组长度
		return this.items.length;
	}

• toString 方法

Queue.prototype.toString = function() {
		let resultString = '';
		// 遍历数组
		for (let i = 0; i < this.items.length; i++) {
			resultString += this.items[i] + ''
		}
		return resultString
	}

---

三、优先级队列结构

1、 封装优先级队列结构及方法

function PriorityQueue() {
	
	// 元素包含两部分 element 数据 priority 优先级
	function QueueElement(element, priority) {
		this.element = element;
		this.priority = priority;
	}
	
	// 封装属性
	this.items = [];
	
	// 实现插入方法
	PriorityQueue.prototype.enqueue = function(element, priority){}
	
	// 其他方法跟队列的一致
}

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

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

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

• 向列表的特定位置插入一个新的项
  
  
  

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

• 获取对应位置的元素

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

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

• 修改某个位置的元素

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;

• 从列表的特定位置移除一项

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

• 其他方法

// 从列表中移除一项
	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、封装链表结构及其方法

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、具体方法实现

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

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

• 向双向链表的特定位置插入一个新的项
  
  
  
  

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

• 获取对应位置的元素

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

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

• 修改某个位置的元素

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

• 返回正反向遍历的节点字符串形式

// 返回正向遍历的节点字符串形式
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();
}

• 从双向链表的特定位置移除一项
  
  
  
  

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

• 其他方法

// 从列表移除一项
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;
}

源码下载 (opens new window)