Stack
Stack （stack） It is a linear table that only inserts and deletes at the end of the table . We call the end that allows insertion and deletion the top of the stack , The other end is called the bottom of the stack , Stacks without any data elements are called empty stacks . Stack is also known as LIFO linear table Because the stack has the characteristics of LIFO , So any element that is not at the top of the stack cannot be accessed . To get the elements at the bottom of the stack , You have to remove the elements first .
The two main operations on the stack are to push an element into the stack and to eject an element from the stack . Put it on the stack push() Method , Out of stack use pop() Method , The following code is used to realize the data structure of stack
Implementation stack class
- dataStore For datasets
top Represents the top coordinate of the stack
class Stack{ dataStore=[] top=0 constructor(){ } }push(): Into the stack
push(element){
this.dataStore[this.top++] = element
}pop(): Out of the stack
pop(){
let element = this.dataStore[--this.top]
this.dataStore.length = this.top
return element
}peek(): Back to the top of the stack
peek(){
return this.dataStore[this.top-1]
}length(): The amount of data
length() {
return this.top;
}clear(): Empty stack
clear() {
this.top = 0;
this.dataStore.length=0
}Complete code
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
A queue is a list , An element that can only be inserted at the end of the queue , Delete the list of elements at the head of the team . Queues are used to store data in order , The two main operations of FIFO queue are ： Insert new elements into the queue and delete elements from the queue . The insert operation is also called team entry , The delete operation is also called out of the queue . The join operation inserts a new element at the end of the team , Delete the element of the head of the team .
The following code is used to implement the queue
Realization Queue class
dataStore For datasets
class Queue {
dataStore = []
constructor() {
}
}enqueue() Method to add an element to the end of the queue
enqueue(element) {
this.dataStore.push(element)
}dequeue() Method to delete the element of the team leader
dequeue() {
return this.dataStore.shift()
}You can use the following method to read the elements at the beginning and end of the team
front() {
return this.dataStore[0]
}
back() {
return this.dataStore[this.dataStore.length - 1]
}toString() Method to display all the elements in the queue
toString() {
return String(this.dataStore)
}Determines if the queue is empty
empty() {
return this.dataStore.length == 0
}Completion code
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
}
}Linked list
A linked list is a set of nodes . Each node uses a reference to an object to point to its successors . A reference to another node is called a chain . Identifying the starting node of the linked list is a little troublesome , Therefore, there is a special node at the front of the linked list , It's called the head node
The designed linked list contains two classes .Node Class to represent a node ,LinkedList Class provides the insertion node 、 Delete node 、 How to display list elements , And other auxiliary methods .
Node class
Nodes contain data and pointers , As shown in the figure below
- element Representative elements
next For the pointer
class Node { constructor(element){ this.element=element this.next=null } }LinkedList class
Create a linked list by default to a head node
class LinkedList {
constructor(){
this.head = new Node('head')
}
}find() Find a node
// Search from the beginning
find(item){
let node = this.head
while(node&&node.element != item){
node = node.next
}
return node
}findPrevious() Find the node before the target
findPrevious(item){
let node = this.head
while(node.next&&node.next.element != item){
node = node.next
}
return node.next?node:null
}insert() Insert new node
Inserting a node is to point the pointer of the new element node to the node pointed to by the target element pointer , Again, the pointer of the target node points to the new node
insert(element,item){
let node = this.find(item)
if(node){
let newNode = new Node(element)
newNode.next = node.next
node.next = newNode
}
}remove() Delete a node
Deleting a node is to point the previous node of the target node to the next node of the target node
remove(item){
let node = this.findPrevious(item)
if(node){
node.next = node.next.next
}
}display() Print linked list
display(){
let node = this.head
while(node){
console.log(node.element)
node = node.next
}
}Complete code
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
}
}
}Double linked list
Although it's easy to traverse from the head node to the tail node of the list , But, in turn, , Traversing from the back to the front is not that easy . By giving Node Object to add an attribute , This property stores links to the precursor node , It's much easier . At this point, it takes more work to insert a node into the linked list , We need to point out the correct precursor and successor of this node . But when you delete a node from the list , Improve the efficiency , There is no need to find the precursor node of the node to be deleted
Node class
The node of the two-way linked list has one more precursor pointer than the node of the one-way linked list previous
class Node {
constructor(element){
this.element=element
this.next=null
this.previous = null
}
}To realize two-way linked list
class DoubleLink{
constructor(){
this.head = new Node('head')
}
}Find an element
find(item){
let node = this.head
while(node&&node.element != item){
node = node.next
}
return node
}Find the previous element
findPrevious(item){
let node = this.head
while(node.next&&node.next.element != item){
node = node.next
}
return node.next?node:null
}Find the last element
findLast(){
let node = this.head
while(node.next){
node = node.next
}
return node
}Insert an element
Insert node , In addition to the same operation as one-way linked list , The precursor pointer of the latter node must point to the node to be inserted , The precursor pointer of the inserted node needs to point to the previous 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
}
}Delete an element
remove(item){
let node = this.findPrevious(item)
if(node){
if(node.next.next){
node.next.next.previous = node
}
node.next = node.next.next
}
}Print elements
display(){
let node = this.head
while(node){
console.log(node.element)
node = node.next
}
}Reverse printing linked list
dispReverse(){
let node = this.findLast()
while(node){
console.log(node.element)
node = node.previous
}
}Complete code
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
}
}
}