點(diǎn)擊下載
本文文檔

當(dāng)前位置：首頁(yè) - 科技 - 知識(shí)百科 - 正文

js棧、隊(duì)列、鏈表數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)代碼分享

來(lái)源：懂視網(wǎng) 責(zé)編：小采時(shí)間：2020-11-27 20:03:10

js棧、隊(duì)列、鏈表數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)代碼分享

js棧、隊(duì)列、鏈表數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)代碼分享:數(shù)據(jù)結(jié)構(gòu)有講過(guò)，棧是一種遵從后進(jìn)先出原則的有序集合，書中對(duì)棧的形容非常到位，就像是堆盤子，先放的肯定在下面的位置，最上面的是才放的。給棧內(nèi)添加元素，最先添加的在棧底，最后一個(gè)加進(jìn)去的稱為棧頂元素。js實(shí)現(xiàn)棧及其方法具體內(nèi)容有創(chuàng)建棧：在js里我們

推薦度：

點(diǎn)擊下載本文 文檔為doc格式

導(dǎo)讀js棧、隊(duì)列、鏈表數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)代碼分享:數(shù)據(jù)結(jié)構(gòu)有講過(guò)，棧是一種遵從后進(jìn)先出原則的有序集合，書中對(duì)棧的形容非常到位，就像是堆盤子，先放的肯定在下面的位置，最上面的是才放的。給棧內(nèi)添加元素，最先添加的在棧底，最后一個(gè)加進(jìn)去的稱為棧頂元素。js實(shí)現(xiàn)棧及其方法具體內(nèi)容有創(chuàng)建棧：在js里我們

數(shù)據(jù)結(jié)構(gòu)有講過(guò)，棧是一種遵從后進(jìn)先出原則的有序集合，書中對(duì)棧的形容非常到位，就像是堆盤子，先放的肯定在下面的位置，最上面的是才放的。給棧內(nèi)添加元素，最先添加的在棧底，最后一個(gè)加進(jìn)去的稱為棧頂元素。

js實(shí)現(xiàn)棧及其方法

具體內(nèi)容有

創(chuàng)建棧：在js里我們用數(shù)組類比棧

向棧里添加元素push()

移除元素 delete()

棧大小 size()

查看棧頂元素 peek()

檢查棧是否為空 isEmpty()

清空棧 empty()

打印棧 print()

使用

代碼

 function Stack(){
 var stack=[]; this.push=function(para){
 stack.push(para);
 }; this.delete=function(){
 // 刪除棧頂元素
 stack.pop();//刪除數(shù)組末尾元素，
 } this.size=function(){
 return stack.length;
 } this.peek=function(){
 return stack[stack.length-1];
 } this.isEmpty=function(){
 if(stack.length==0){ return true;
 }else{ return false;
 }
 } this.emptyStack=function(){
 stack=[];
 } this.print=function(){
 return stack.toString();
 }
}

使用

var myStack=new Stack();
myStack.push(1);
myStack.push(4);
myStack.push(6);
console.log('刪除前棧內(nèi)元素'+myStack.print());
console.log('刪除前棧頂元素'+myStack.peek());
console.log('刪除前棧元素size'+myStack.size());
myStack.delete();
console.log('刪除后棧內(nèi)元素'+myStack.print());
console.log('刪除后棧頂元素'+myStack.peek());
console.log('刪除前棧元素size'+myStack.size());
console.log('棧是否為空'+myStack.isEmpty());
myStack.emptyStack();
console.log('清空棧，棧是否為空'+myStack.isEmpty());
console.log('清空棧,棧元素size'+myStack.size());

這里寫圖片描述

隊(duì)列

先進(jìn)先出，就像喝孟婆湯要排隊(duì)一樣，先來(lái)的排在前面，后面來(lái)的就排在隊(duì)尾，要投胎肯定是前面喝完的人去，操作隊(duì)列也一樣，從隊(duì)列前面移除元素，從隊(duì)尾添加元素。和棧的實(shí)現(xiàn)大同小異

function Queue(){
 var queue=[]; this.push=function(para){
 queue.push(para);
 } this.delete=function(){
 // 從隊(duì)首移除，即刪除的是數(shù)組第一位
 queue.shift();
 } this.queueFront=function(){
 return queue[0];
 } this.isEmpty=function(){
 if(queue.length==0){ return true;
 }else{ return false;
 }
 } this.size=function(){
 return queue.length;
 } this.emptyQueue=function(){
 queue=[];
 } this.print=function(){
 return queue.toString();
 }
}var myQueue=new Queue();
myQueue.push(1);
myQueue.push(4);
myQueue.push(6);
console.log('刪除前隊(duì)列內(nèi)元素'+myQueue.print());
console.log('刪除前隊(duì)列頂元素'+myQueue.queueFront());
console.log('刪除前隊(duì)列元素size'+myQueue.size());
myQueue.delete();
console.log('刪除后隊(duì)列內(nèi)元素'+myQueue.print());
console.log('刪除后隊(duì)列頂元素'+myQueue.queueFront());
console.log('刪除前隊(duì)列元素size'+myQueue.size());
console.log('隊(duì)列是否為空'+myQueue.isEmpty());
myQueue.emptyQueue();
console.log('清空隊(duì)列，隊(duì)列是否為空'+myQueue.isEmpty());
console.log('清空隊(duì)列,隊(duì)列元素size'+myQueue.size());

這里寫圖片描述

實(shí)現(xiàn)的不同點(diǎn)

刪除操作和訪問(wèn)隊(duì)首（棧頂）元素的方法不一樣，這是由于后進(jìn)先出和先進(jìn)先出的原則不同造成的，棧刪除的是數(shù)組最后一位( pop() )，隊(duì)列刪除數(shù)組的第一位（shift()）,棧頂元素是數(shù)組最后一位，而隊(duì)列的隊(duì)首元素是數(shù)組第一位元素。

書上有用ES6的新特性寫的實(shí)現(xiàn)方式，emmmm我ES6不甚了解，等以后以后以后~~~

補(bǔ)充，優(yōu)先隊(duì)列

說(shuō)白了就是有特權(quán)，書中規(guī)定優(yōu)先級(jí)小的在前面。然后自己實(shí)現(xiàn)了一下，代碼和書中不太一樣，兩個(gè)都運(yùn)行了一下
先貼一下書上的代碼

function PriorityQueue(){
 let items=[]; function QueueElement(element,priority){
 this.element=element; this.priority=priority;
 } this.enqueue=function(element,priority){
 let queueElement=new QueueElement(element, priority); let added=false; for(let i=0;i<items.length;i++){ if(queueElement.priority<isFinite([i].priority)){
 items.splice(i,0,queueElement);
 added=true; break;
 }
 } if(!added){
 items.push(queueElement);
 }
 }; this.print=function(){
 return items;
 }
}var pq=new PriorityQueue();
pq.enqueue('aa',2);
pq.enqueue('aba',4);
pq.enqueue('jjjj',8);
pq.enqueue('aaaaaaa',8);
pq.enqueue('aa',-1);
console.log(pq.print());

這里寫圖片描述

function PriorityQueue(){
 // 按優(yōu)先級(jí)從小到大排列，
 var queue=[]; function QueueElement(ele,prior){
 this.element=ele; this.prior=prior;
 } this.enqueue=function(ele,prior){
 //循環(huán)遍歷隊(duì)列內(nèi)所有元素，如果當(dāng)前優(yōu)先級(jí)小，則放在該位之前
 var curr=new QueueElement(ele, prior); if(queue.length==0){
 queue.push(curr);
 }else{ if(curr.prior<=queue[0].prior){
 queue.splice(0,0,curr);
 }else{
 queue.push(curr);
 }
 }
 } this.print=function(){
 return queue;
 }
}var pq=new PriorityQueue();
pq.enqueue('aa',2);
pq.enqueue('aba',4);
pq.enqueue('jjjj',8);
pq.enqueue('aaaaaaa',8);
pq.enqueue('aa',-1);
console.log(pq.print());

這里寫圖片描述

嗷嗷嗷截完圖才發(fā)現(xiàn)最后應(yīng)該輸出element，不要優(yōu)先級(jí)，這里補(bǔ)一下上面兩個(gè)的print方法（注意，我聲明的是queue，書中是items ^_^）

this.print=function(){
 var result=[]; for(let j = 0, length2 = items.length; j < length2; j++){
 result[j]=items[j].element;
 }
 return result;
 }

鏈表

鏈表存儲(chǔ)有序的元素集合，但不同于數(shù)組的是，鏈表中的元素并不是連續(xù)放置的。每個(gè)元素由存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用（指針）構(gòu)成，

單鏈表

鏈表類的方法都有：

append(para) 在鏈表尾部添加元素appendAt(element,index) 在指定位置添加元素deleteAt(index) 刪除指定位置的鏈表元素getHead() 獲得鏈表頭元素size() 獲得鏈表大小print() 打印出鏈表內(nèi)容 

toString()

輸出鏈表元素的內(nèi)容indexOf(para) 查找元素如果在鏈表中找到了就返回他的位置，沒(méi)找到就返回-1isEmpty() 判斷鏈表是否為空size() 獲取鏈表長(zhǎng)度

具體代碼

因?yàn)槭菍懸欢螠y(cè)試一段，所以函數(shù)沒(méi)在一起寫，先分開后面再匯總。

function LinkList(){
 let Node=function(element){
 this.element=element; this.next=null;
 }; var list=[];
 let length=0;
 let head=null;
 let currNode=null; this.append=function(para){
 //鏈表尾部追加元素
 var node=new Node(para); var current;//一直指向上一個(gè)添加的節(jié)點(diǎn)
 if(head==null){ //插入第一個(gè)元素
 head=node;
 currNode=head; // console.log(head);

 }else{ //不是第一個(gè)元素
 //上一個(gè)的next指針指向當(dāng)前node；
 currNode.next=node; // console.log(currNode);
 currNode=node;
 }
 length++; // list.push(node);
 } this.getHead=function(){
 return head;
 } this.appendAt=function(element,index){
 if(index>=0 && index<=length){ var node=new Node(element); var current=head; var previous; var position=0; if(index==0){
 node.next=current;
 head=node;
 }else{ while(position++<index){
 previous=current;
 current=current.next
 }
 node.next=current;
 previous.next=node;
 }
 length++; // return 
 }else{
 alert("參數(shù)錯(cuò)誤");
 }
 } this.deleteAt=function(index){
 //從特定位置移除一個(gè)元素，index索引
 if(index>=0 && index<length){ var previousNode=null; var node=head; var position=0; if(index==0){
 head=node.next; return node.element;
 }else{ // console.log(node);
 while(position++<index){ // console.log(node);
 previousNode=node;
 node=node.next;
 }
 previousNode.next=node.next; return node.element;
 }
 }else{
 alert("參數(shù)不正確！"); return null;
 }

 length--;
 } this.size=function(){
 return list.length;
 } this.print=function(){
 var result=[]; for(let i = 0, length1 = list.length; i < length1; i++){
 result[i]=list[i];
 } return result;
 }
}

var linkList=new LinkList();
linkList.append('lorry1');
linkList.append('lorry2');
linkList.append('lorry3');
linkList.appendAt('lorry4',0);

linkList.appendAt('lorry5',0);// 那么當(dāng)前鏈表的元素順序是 lorry5，lorry4，lorry1，lorry2，lorry3console.log(linkList.deleteAt(2));
console.log(linkList.getHead().next);//獲取頭元素的下一個(gè)元素

控制臺(tái)打印出來(lái)的內(nèi)容：lorry1 linkList.js:112 Node {element: "lorry4", next: Node} linkList.js:115 
 element:"lorry4"
 next:Node {element: "lorry2", next: Node}
 __proto__:Object

這里寫圖片描述
toString，size，indexOf方法

this.toString=function(){
 var current=head; var str=''; var i=0; while(current){
 str+=current.element+' ';
 current=current.next;
 } return str;
 } this.indexOf=function(para){
 //返回首個(gè)出現(xiàn)該參數(shù)的位置
 var current=head; var index=-1; // var i=0;
 while(current){
 index+=1; if(current.element==para){ return index;
 }
 current=current.next;
 } return -1;
 } this.isEmpty=function(){
 return length==0;
 } this.size=function(){
 return length;
 }

var linkList=new LinkList();
linkList.append('lorry1');
linkList.append('lorry2');
linkList.append('lorry3');
linkList.appendAt('lorry4',0);
linkList.appendAt('lorry5',1);

linkList.appendAt('lorry5',0);console.log('我刪除了...'+linkList.deleteAt(1));console.log('頭元素下一個(gè)元素是...'+linkList.getHead().next.element);console.log('刪除后鏈表內(nèi)容...'+linkList.toString());console.log('lorry5在鏈表中的位置...'+linkList.indexOf('lorry5'));console.log('lorriy5在鏈表中的位置....'+linkList.indexOf('lorriy5'));console.log('鏈表長(zhǎng)度...'+linkList.size());

linkList.js:143 我刪除了...lorry4linkList.js:145 頭元素下一個(gè)元素是...lorry5linkList.js:146 刪除后鏈表內(nèi)容...lorry5 lorry5 lorry1 lorry2 lorry3 
linkList.js:147 lorry5在鏈表中的位置...0linkList.js:148 lorriy5在鏈表中的位置....-1linkList.js:150 鏈表長(zhǎng)度...5

這里寫圖片描述