數(shù)據(jù)結(jié)構(gòu)有講過(guò),棧是一種遵從后進(jìn)先出原則的有序集合,書中對(duì)棧的形容非常到位,就像是堆盤子,先放的肯定在下面的位置,最上面的是才放的。給棧內(nèi)添加元素,最先添加的在棧底,最后一個(gè)加進(jì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());
先進(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());
刪除操作和訪問(wèn)隊(duì)首(棧頂)元素的方法不一樣,這是由于后進(jìn)先出和先進(jìn)先出的原則不同造成的,棧刪除的是數(shù)組最后一位( pop() ),隊(duì)列刪除數(shù)組的第一位(shift()),棧頂元素是數(shù)組最后一位,而隊(duì)列的隊(duì)首元素是數(shù)組第一位元素。
書上有用ES6的新特性寫的實(shí)現(xiàn)方式,emmmm我ES6不甚了解,等以后以后以后~~~
說(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()
具體代碼
因?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
聲明:本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí),若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系,我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com