資料結構有講過,堆疊是一種遵從後進先出原則的有序集合,書中對棧的形容非常到位,就像是堆盤子,先放的肯定在下面的位置,最上面的是才放的。在棧內加入元素,最先加入的在棧底,最後一個加進去的稱為棧頂元素。
具體內容有
#建立堆疊:在js裡我們用陣列類別比堆疊
#新增元素push()
# #
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##############相關推薦:######### PHP實作堆疊資料結構與括號匹配############PHP使用兩個堆疊實作佇列功能############php線性資料表的入棧與出棧詳解######
以上是js堆疊、佇列、鍊錶資料結構的實作程式碼分享的詳細內容。更多資訊請關注PHP中文網其他相關文章!