點擊下載
本文文檔

當前位置：首頁 - 科技 - 知識百科 - 正文

js棧、隊列、鏈表數據結構的實現代碼分享

來源：懂視網責編：小采時間：2020-11-27 20:03:10

js棧、隊列、鏈表數據結構的實現代碼分享

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

推薦度：

點擊下載本文 文檔為doc格式

導讀js棧、隊列、鏈表數據結構的實現代碼分享:數據結構有講過，棧是一種遵從后進先出原則的有序集合，書中對棧的形容非常到位，就像是堆盤子，先放的肯定在下面的位置，最上面的是才放的。給棧內添加元素，最先添加的在棧底，最后一個加進去的稱為棧頂元素。js實現棧及其方法具體內容有創建棧：在js里我們

數據結構有講過，棧是一種遵從后進先出原則的有序集合，書中對棧的形容非常到位，就像是堆盤子，先放的肯定在下面的位置，最上面的是才放的。給棧內添加元素，最先添加的在棧底，最后一個加進去的稱為棧頂元素。

js實現棧及其方法

具體內容有

創建棧：在js里我們用數組類比棧

向棧里添加元素push()

移除元素 delete()

棧大小 size()

查看棧頂元素 peek()

檢查棧是否為空 isEmpty()

清空棧 empty()

打印棧 print()

使用

代碼

 function Stack(){
 var stack=[]; this.push=function(para){
 stack.push(para);
 }; this.delete=function(){
 // 刪除棧頂元素
 stack.pop();//刪除數組末尾元素，
 } 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('刪除前棧內元素'+myStack.print());
console.log('刪除前棧頂元素'+myStack.peek());
console.log('刪除前棧元素size'+myStack.size());
myStack.delete();
console.log('刪除后棧內元素'+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());

這里寫圖片描述

隊列

先進先出，就像喝孟婆湯要排隊一樣，先來的排在前面，后面來的就排在隊尾，要投胎肯定是前面喝完的人去，操作隊列也一樣，從隊列前面移除元素，從隊尾添加元素。和棧的實現大同小異

function Queue(){
 var queue=[]; this.push=function(para){
 queue.push(para);
 } this.delete=function(){
 // 從隊首移除，即刪除的是數組第一位
 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('刪除前隊列內元素'+myQueue.print());
console.log('刪除前隊列頂元素'+myQueue.queueFront());
console.log('刪除前隊列元素size'+myQueue.size());
myQueue.delete();
console.log('刪除后隊列內元素'+myQueue.print());
console.log('刪除后隊列頂元素'+myQueue.queueFront());
console.log('刪除前隊列元素size'+myQueue.size());
console.log('隊列是否為空'+myQueue.isEmpty());
myQueue.emptyQueue();
console.log('清空隊列，隊列是否為空'+myQueue.isEmpty());
console.log('清空隊列,隊列元素size'+myQueue.size());

這里寫圖片描述

實現的不同點

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

書上有用ES6的新特性寫的實現方式，emmmm我ES6不甚了解，等以后以后以后~~~

補充，優先隊列

說白了就是有特權，書中規定優先級小的在前面。然后自己實現了一下，代碼和書中不太一樣，兩個都運行了一下
先貼一下書上的代碼

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(){
 // 按優先級從小到大排列，
 var queue=[]; function QueueElement(ele,prior){
 this.element=ele; this.prior=prior;
 } this.enqueue=function(ele,prior){
 //循環遍歷隊列內所有元素，如果當前優先級小，則放在該位之前
 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());

這里寫圖片描述

嗷嗷嗷截完圖才發現最后應該輸出element，不要優先級，這里補一下上面兩個的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;
 }

鏈表

鏈表存儲有序的元素集合，但不同于數組的是，鏈表中的元素并不是連續放置的。每個元素由存儲元素本身的節點和一個指向下一個元素的引用（指針）構成，

單鏈表

鏈表類的方法都有：

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

toString()

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

具體代碼

因為是寫一段測試一段，所以函數沒在一起寫，先分開后面再匯總。

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;//一直指向上一個添加的節點
 if(head==null){ //插入第一個元素
 head=node;
 currNode=head; // console.log(head);

 }else{ //不是第一個元素
 //上一個的next指針指向當前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("參數錯誤");
 }
 } this.deleteAt=function(index){
 //從特定位置移除一個元素，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("參數不正確！"); 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);// 那么當前鏈表的元素順序是 lorry5，lorry4，lorry1，lorry2，lorry3console.log(linkList.deleteAt(2));
console.log(linkList.getHead().next);//獲取頭元素的下一個元素

控制臺打印出來的內容：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){
 //返回首個出現該參數的位置
 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('頭元素下一個元素是...'+linkList.getHead().next.element);console.log('刪除后鏈表內容...'+linkList.toString());console.log('lorry5在鏈表中的位置...'+linkList.indexOf('lorry5'));console.log('lorriy5在鏈表中的位置....'+linkList.indexOf('lorriy5'));console.log('鏈表長度...'+linkList.size());

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

這里寫圖片描述