js 스택, 큐 및 연결 목록 데이터 구조의 구현 코드 공유

小云云
풀어 주다: 2018-02-26 15:17:08
원래의
1517명이 탐색했습니다.

데이터 구조는 앞서 언급한 바 있습니다. 스택은 후입선출 원칙을 따르는 정렬된 컬렉션입니다. 책에 있는 스택에 대한 설명은 접시 더미처럼 매우 정확합니다. 아래쪽에 있어야 하고 위쪽은 아래쪽에 배치해야 합니다. 요소가 스택에 추가되면 추가된 첫 번째 요소는 스택의 맨 아래에 있고 마지막으로 추가된 요소를 맨 위 요소라고 합니다.

js는 스택과 그 메소드를 구현합니다

구체적인 내용은

  • 스택 생성: js에서는 스택에 비유하여 배열을 사용합니다

  • 스택에 요소 추가 push()

  • 요소 제거 delete()

  • 스택 크기 size()

  • 스택의 최상위 요소 보기 peek()

  • 스택이 비어 있는지 확인 isEmpty()

  • 스택 비우기()

  • print stack 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();
    }
}
로그인 후 복사
js 스택, 큐 및 연결 목록 데이터 구조의 구현 코드 공유use

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());
로그인 후 복사

queueaue

js 스택, 큐 및 연결 목록 데이터 구조의 구현 코드 공유 first, 먼저, Meng Po Soup, 오는 사람들 먼저 오는 사람이 줄을 서게 되며, 대기열이 끝나면 앞에서 술을 다 마신 사람이 환생해야 합니다. 작업 대기열에서도 마찬가지입니다. 큐와 요소는 큐의 끝에서부터 추가됩니다. 구현은 스택과 거의 동일합니다

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());
로그인 후 복사

구현의 차이

삭제 작업과 첫 번째(스택의 최상위) 요소에 액세스하는 방법이 다릅니다. 이는 마지막의 원칙이 다르기 때문입니다. -in-first-out 및 first-in-first-out. 삭제되는 것은 배열의 마지막 비트(pop())이고 큐는 배열의 첫 번째 비트(shift())를 삭제합니다. 스택의 최상위 요소는 배열의 마지막 비트이고 큐의 첫 번째 요소는 배열의 첫 번째 요소입니다.

이 책은 ES6의 새로운 기능으로 작성된 구현 방법을 사용합니다. 음, ES6에 대해서는 잘 모릅니다. 앞으로 지켜보겠습니다~~~


게다가 우선 순위 대기열

직접 말하면 , 책에는 우선 순위가 더 낮은 것이 Front라고 규정되어 있습니다. 그러다가 제가 직접 구현한 코드가 책에 나온 코드와 다릅니다. 먼저 책에 코드를 올려보세요. js 스택, 큐 및 연결 목록 데이터 구조의 구현 코드 공유

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(&#39;aa&#39;,2);
pq.enqueue(&#39;aba&#39;,4);
pq.enqueue(&#39;jjjj&#39;,8);
pq.enqueue(&#39;aaaaaaa&#39;,8);
pq.enqueue(&#39;aa&#39;,-1);
console.log(pq.print());
로그인 후 복사

js 스택, 큐 및 연결 목록 데이터 구조의 구현 코드 공유

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(&#39;aa&#39;,2);
pq.enqueue(&#39;aba&#39;,4);
pq.enqueue(&#39;jjjj&#39;,8);
pq.enqueue(&#39;aaaaaaa&#39;,8);
pq.enqueue(&#39;aa&#39;,-1);
console.log(pq.print());
로그인 후 복사

요소는 마지막에 출력되어야 합니다. 우선 순위는 없습니다. 위 두 가지의 인쇄 방법은 다음과 같습니다. (참고, 대기열을 선언했는데 책에서는 항목입니다 ^_^)

this.print=function(){
        var result=[];        for(let j = 0, length2 = items.length; j < length2; j++){
            result[j]=items[j].element;
        }
        return result;
    }
로그인 후 복사

Linked list

Linked list는 순서가 지정된 컬렉션을 저장합니다. 요소의 배열과 다르지만 연결리스트의 요소는 연속적으로 배치되지 않습니다. 각 요소는 요소 자체를 저장하는 노드와 다음 요소를 가리키는 참조(포인터)로 구성됩니다.

단일 연결 목록

연결 목록 클래스의 메서드에는 다음이 포함됩니다.

append(para) 在链表尾部添加元素appendAt(element,index) 在指定位置添加元素deleteAt(index) 删除指定位置的链表元素getHead() 获得链表头元素size() 获得链表大小print() 打印出链表内容 

toString() 输出链表元素的内容indexOf(para)  查找元素如果在链表中找到了就返回他的位置,没找到就返回-1isEmpty() 判断链表是否为空size()  获取链表长度
로그인 후 복사

특정 코드

문단을 작성하는 것이기 때문에 기능이 함께 작성되지 않도록 섹션을 테스트하여 먼저 분리한 후 나중에 요약합니다. js 스택, 큐 및 연결 목록 데이터 구조의 구현 코드 공유

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(&#39;lorry1&#39;);
linkList.append(&#39;lorry2&#39;);
linkList.append(&#39;lorry3&#39;);
linkList.appendAt(&#39;lorry4&#39;,0);

linkList.appendAt(&#39;lorry5&#39;,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 메서드js 스택, 큐 및 연결 목록 데이터 구조의 구현 코드 공유

this.toString=function(){
        var current=head;        var str=&#39;&#39;;        var i=0;        while(current){
            str+=current.element+&#39; &#39;;
            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(&#39;lorry1&#39;);
linkList.append(&#39;lorry2&#39;);
linkList.append(&#39;lorry3&#39;);
linkList.appendAt(&#39;lorry4&#39;,0);
linkList.appendAt(&#39;lorry5&#39;,1);

linkList.appendAt(&#39;lorry5&#39;,0);console.log(&#39;我删除了...&#39;+linkList.deleteAt(1));console.log(&#39;头元素下一个元素是...&#39;+linkList.getHead().next.element);console.log(&#39;删除后链表内容...&#39;+linkList.toString());console.log(&#39;lorry5在链表中的位置...&#39;+linkList.indexOf(&#39;lorry5&#39;));console.log(&#39;lorriy5在链表中的位置....&#39;+linkList.indexOf(&#39;lorriy5&#39;));console.log(&#39;链表长度...&#39;+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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!