一、栈结构
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;
}
