点击下载
本文文档

当前位置：首页 - 科技 - 知识百科 - 正文

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

这里写图片描述