js栈、队列、链表数据结构的实现代码分享

js栈、队列、链表数据结构的实现代码分享,第1张

数据结构有讲过,栈是一种遵从后进先出原则的有序集合,书中对栈的形容非常到位,就像是堆盘子,先放的肯定在下面的位置,最上面的是才放的。给栈内添加元素,最先添加的在栈底,最后一个加进去的称为栈顶元素。

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());

js栈、队列、链表数据结构的实现代码分享,这里写图片描述,第2张

队列

先进先出,就像喝孟婆汤要排队一样,先来的排在前面,后面来的就排在队尾,要投胎肯定是前面喝完的人去,操作队列也一样,从队列前面移除元素,从队尾添加元素。和栈的实现大同小异

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());

js栈、队列、链表数据结构的实现代码分享,这里写图片描述,第3张

实现的不同点

删除操作和访问队首(栈顶)元素的方法不一样,这是由于后进先出和先进先出的原则不同造成的,栈删除的是数组最后一位( 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());

js栈、队列、链表数据结构的实现代码分享,这里写图片描述,第4张

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());

js栈、队列、链表数据结构的实现代码分享,这里写图片描述,第5张

嗷嗷嗷 截完图才发现最后应该输出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

js栈、队列、链表数据结构的实现代码分享,这里写图片描述,第6张
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

js栈、队列、链表数据结构的实现代码分享,这里写图片描述,第7张

相关推荐:

PHP实现栈数据结构和括号匹配

PHP使用两个栈实现队列功能

php线性表的入栈与出栈详解

以上就是js栈、队列、链表数据结构的实现代码分享的详细内容,更多请关注php中文网其它相关文章!

文章来源:https://www.php.cn/faq/387069.html

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复