前言
常言说，打蛇打七寸，学习数据结构，关键要理解数据结构特点以及每种结构的增、删、查方法
一、队列
1.普通队列
特点
先进先出
方法
方法 | 描述 |
|---|---|
push | 队列末尾追加元素 |
shift | 删除队列最后一个元素 |
实现
代码语言：javascript复制// 普通队列
class Queue {
constructor(){
this.list = [];
}
push(element){
this.list.push(element);
}
shift(){
return this.list.shift();
}
front(){
return this.list[0];
}
back(){
return this.list[this.list.length-1];
}
display(){
return this.list.toString();
}
isEmpty(){
return this.list.length == 0
}
}对于前端，队列可以说是最简单的数据结构了，因为JavaScript的数组Array是天生支持队列，因为数组自带push、shift、pop、unshift方法
2.优先队列
特点
优先级一样时先进先出，否则优先级最高的先出
方法
方法 | 描述 |
|---|---|
push | 队列末尾追加元素 |
pop | 删除队列级最高的一个元素，否则删除首位 |
实现
代码语言：javascript复制// 优先队列
class PriQueue {
constructor(element, priority){
this.element = element;
this.priority = priority; // 记录优先级
}
push(element){
this.list.push(element);
}
shift(){
let priority = this.list[0].priority;
let index = 0;
for (let i = 0; i < this.list.length; i ) {
if ( this.list[i].priority > priority ) {
priority = this.list[i].priority;
index = i;
}
}
return this.list.splice(index, index 1)
}
isEmpty(){
return this.list.length == 0
}
}二、栈
特点
先进后出或者后进先出
方法
方法 | 描述 |
|---|---|
push | 栈末尾追加元素 |
pop | 弹出栈末尾的一个元素 |
实现
代码语言：javascript复制class Stack {
constructor(){
this.list = [];
this.depth = 0; // 记录深度
}
push(element){
this.list[this.depth] = element;
this.depth = 1;
}
pop(){
this.depth -= 1;
return this.list[this.depth];
}
peek(){
return this.list[this.depth-1]
}
length(){
return this.depth;
}
clear(){
this.list = [];
}
}三、链表
链式存储的非连续数据结构
1.单向链表
特点
每个元素只能和上一个元素或下一个元素连接
方法
方法 | 描述 |
|---|---|
find | 查找某一个元素 |
findPro | 查找前一个元素 |
insert | 在某个元素后面插入新元素 |
remove | 删除某个元素 |
实现
代码语言：javascript复制 // 单向链表
class Node {
constructor(element){
this.element = element
this.next = null
}
}
class List {
constructor(){
this.head = new Node("head");
}
find(element){
let currNode = this.head;
while(currNode.element != element){
currNode = currNode.next;
}
return currNode;
}
findPro(element){
let proNode = this.head;
while(proNode.next.element != element){
proNode = proNode.next;
}
console.log(proNode);
return proNode;
}
insert(newElement, element){
let newNode = new Node(newElement);
this.find(element).next = newNode;
console.log(newNode)
}
remove(element){
this.findPro(element).next = this.find(element).next;
}
display(){
let currNode = this.head;
while(!(currNode.next == null)){
console.log(currNode.next.element)
currNode = currNode.next;
}
return
}
}
let list = new List();
list.insert("body","head");
list.insert("foot","body");
list.display();
// list.find("gg");
list.remove("body");
list.display();2.双向链表
特点
每个元素不仅和上一个元素而且和下一个元素连接
方法
方法 | 描述 |
|---|---|
find | 查找某一个元素 |
findLast | 查找最后一个元素 |
insert | 在某个元素后面插入新元素 |
remove | 删除某个元素 |
dispReverse | 翻转链表 |
实现
代码语言：javascript复制// 双向链表
class TwoNode {
constructor(element){
this.element = element;
this.next = null;
this.pro = null;
}
}
class TwoList {
constructor(){
this.head = new TwoNode("head");
}
find(element){
let currNode = this.head;
while(currNode.element != element){
if (currNode.next == null) {
}
currNode = currNode.next;
}
return currNode;
}
findLast(){
let currNode = this.head;
while(currNode.next != null){
currNode = currNode.next;
}
return currNode;
}
insert(newElement, element){
let newNode = new TwoNode(newElement);
let currNode = this.find(element)
newNode.next = currNode.next;
newNode.pro = currNode;
currNode.next = newNode;
}
remove(element){
let currNode = this.find(element);
if (!(currNode.next == null)) {
currNode.pro.next = currNode.next;
currNode.next.pro = currNode.pro;
currNode.pro = null;
currNode.next = null;
}
}
display(){
let currNode = this.head;
while(!(currNode.next == null)){
console.log(currNode.next.element)
currNode = currNode.next;
}
return
}
dispReverse(element){
let currNode = this.findLast();
while(!(currNode.element == "head")){
console.log(currNode.element);
currNode = currNode.pro;
}
return
}
}
let list = new TwoList();
list.insert("c","head");
list.insert("b","c");
list.insert("f","b");
list.display();
list.remove("b");
list.display();
list.findLast();
list.dispReverse();3.循环链表
特点
每个元素不仅和上一个元素而且和下一个元素连接，并且首尾相连
方法
方法 | 描述 |
|---|---|
find | 查找某一个元素 |
findLast | 查找最后一个元素 |
insert | 在某个元素后面插入新元素 |
remove | 删除某个元素 |
实现
代码语言：javascript复制// 循环链表
class LoopNode {
constructor(element){
this.element = element;
}
}
class LoopList {
constructor(){
this.head = new LoopNode("head");
this.head.next = this.head;
}
find(element){
let currNode = this.head;
while(currNode.element != element){
currNode = currNode.next;
}
return currNode;
}
findPro(element){
let proNode = this.head;
while(proNode.next.element != element){
proNode = proNode.next;
}
console.log(proNode);
return proNode;
}
insert(newElement, element){
let newNode = new Node(newElement);
this.find(element).next = newNode;
console.log(newNode)
}
remove(element){
this.findPro(element).next = this.find(element).next;
}
display(){
let currNode = this.head;
while(!(currNode.next == null) && !(currNode.next.element == "head")){
console.log(currNode.next.element);
currNode = currNode.next;
}
return
}
}
