栈
栈（stack）是限定仅在表尾进行插入和删除操作的线性表。咱们把容许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表 因为栈具备后入先出的特点，所以任何不在栈顶的元素都无法访问。为了失去栈底的元素，必须先拿掉下面的元素。
对栈的两种次要操作是将一个元素压入栈和将一个元素弹出栈。入栈应用 push()办法，出栈应用 pop()办法，上面用代码实现栈这种数据结构
实现栈类
- dataStore代表数据集
top代表栈顶坐标
class Stack{ dataStore=[] top=0 constructor(){ }}push():进栈
push(element){ this.dataStore[this.top++] = element }pop():出栈
pop(){ let element = this.dataStore[--this.top] this.dataStore.length = this.top return element }peek():返回栈顶
peek(){ return this.dataStore[this.top-1] }length():数据的数量
length() { return this.top; }clear():清空栈
clear() { this.top = 0; this.dataStore.length=0 }残缺代码
class Stack { dataStore = [] top = 0 constructor() { } push(element) { this.dataStore[this.top++] = element } pop() { let element = this.dataStore[--this.top] this.dataStore.length = this.top return element } peek() { return this.dataStore[this.top - 1] } length() { return this.top; } clear() { this.top = 0; this.dataStore.length = 0 }}队列
队列是一种列表，一种只能在队尾插入元素，在队首删除元素的列表。队列用于存储按顺序排列的数据，先进先出队列的两种次要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。
上面用代码实现队列
实现 Queue 类
dataStore代表数据集
class Queue { dataStore = [] constructor() { }}enqueue() 办法向队尾增加一个元素
enqueue(element) { this.dataStore.push(element) }dequeue() 办法删除队首的元素
dequeue() { return this.dataStore.shift() }能够应用如下办法读取队首和队尾的元素
front() { return this.dataStore[0]}back() { return this.dataStore[this.dataStore.length - 1]}toString() 办法显示队列内的所有元素
toString() { return String(this.dataStore) }判断队列是否为空
empty() { return this.dataStore.length == 0 }实现代码
class Queue { dataStore = [] constructor() { } enqueue(element) { this.dataStore.push(element) } dequeue() { return this.dataStore.shift() } front() { return this.dataStore[0] } back() { return this.dataStore[this.dataStore.length - 1] } toString() { return String(this.dataStore) } empty() { return this.dataStore.length == 0 }}链表
链表是由一组节点组成的汇合。每个节点都应用一个对象的援用指向它的后继。指向另一个节点的援用叫做链。标识出链表的起始节点却有点麻烦，因而在链表最后面有一个非凡节点，叫做头节点
设计的链表蕴含两个类。Node类用来示意节点，LinkedList类提供了插入节点、删除节点、显示列表元素的办法，以及其余一些辅助办法。
Node类
节点蕴含数据和指针，如下图所示
- element代表元素
next为指针
class Node { constructor(element){ this.element=element this.next=null }}LinkedList类
链表创立默认给个头结点
class LinkedList { constructor(){ this.head = new Node('head') }}find()查找一个节点
//从头遍历开始查找find(item){ let node = this.head while(node&&node.element != item){ node = node.next } return node }findPrevious()查找指标前一个节点
findPrevious(item){ let node = this.head while(node.next&&node.next.element != item){ node = node.next } return node.next?node:null }insert()插入新节点
插入节点是将新元素节点的指针指向指标元素指针指向的节点，再讲指标节点的指针指向新节点
insert(element,item){ let node = this.find(item) if(node){ let newNode = new Node(element) newNode.next = node.next node.next = newNode } }remove()删除一个节点
删除节点是将指标节点的上一个节点指向指标节点的下一个节点
remove(item){ let node = this.findPrevious(item) if(node){ node.next = node.next.next } }display()打印链表
display(){ let node = this.head while(node){ console.log(node.element) node = node.next } }残缺代码
class Node { constructor(element) { this.element = element this.next = null }}class LinkedList { constructor() { this.head = new Node('head') } find(item) { let node = this.head while (node && node.element != item) { node = node.next } return node } findPrevious(item) { let node = this.head while (node.next && node.next.element != item) { node = node.next } return node.next ? node : null } insert(element, item) { let node = this.find(item) if (node) { let newNode = new Node(element) newNode.next = node.next node.next = newNode } } remove(item) { let node = this.findPrevious(item) if (node) { node.next = node.next.next } } display() { let node = this.head while (node) { console.log(node.element) node = node.next } }}双向链表
只管从链表的头节点遍历到尾节点很简略，但反过来，从后向前遍历则没那么简略。通过给Node对象减少一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时向链表插入一个节点须要更多的工作，咱们须要指出该节点正确的前驱和后继。然而在从链表中删除节点时，效率进步了，不须要再查找待删除节点的前驱节点了
Node类
双向链表的节点比单向链表的节点多了一个前驱指针previous
class Node { constructor(element){ this.element=element this.next=null this.previous = null }}实现双向链表
class DoubleLink{ constructor(){ this.head = new Node('head') }}查找一个元素
find(item){ let node = this.head while(node&&node.element != item){ node = node.next } return node }查找前一个元素
findPrevious(item){ let node = this.head while(node.next&&node.next.element != item){ node = node.next } return node.next?node:null }查找最初一个元素
findLast(){ let node = this.head while(node.next){ node = node.next } return node }插入一个元素
插入节点，除了和单向链表一样的操作外，后一个节点的前驱指针得指向要插入的节点，插入的节点的前驱指针须要指向前一个节点
insert(element,item){ let node = this.find(item) if(node){ let newNode = new Node(element) newNode.previous = node if( node.next){ node.next.previous = newNode } newNode.next = node.next node.next = newNode } }删除一个元素
remove(item){ let node = this.findPrevious(item) if(node){ if(node.next.next){ node.next.next.previous = node } node.next = node.next.next } }打印元素
display(){ let node = this.head while(node){ console.log(node.element) node = node.next } }逆向打印链表
dispReverse(){ let node = this.findLast() while(node){ console.log(node.element) node = node.previous } }残缺代码
class Node { constructor(element) { this.element = element this.next = null this.previous = null }}class DoubleLink { constructor() { this.head = new Node('head') } find(item) { let node = this.head while (node && node.element != item) { node = node.next } return node } findPrevious(item) { let node = this.head while (node.next && node.next.element != item) { node = node.next } return node.next ? node : null } findLast() { let node = this.head while (node.next) { node = node.next } return node } insert(element, item) { let node = this.find(item) if (node) { let newNode = new Node(element) newNode.previous = node if (node.next) { node.next.previous = newNode } newNode.next = node.next node.next = newNode } } remove(item) { let node = this.findPrevious(item) if (node) { if (node.next.next) { node.next.next.previous = node } node.next = node.next.next } } display() { let node = this.head while (node) { console.log(node.element) node = node.next } } dispReverse() { let node = this.findLast() while (node) { console.log(node.element) node = node.previous } }}