집 >웹 프론트엔드 >JS 튜토리얼 >JS를 사용하여 getMin 함수로 스택을 구현하는 방법

JS를 사용하여 getMin 함수로 스택을 구현하는 방법

不言원래의: 2018-07-17 17:08:562053검색

이 글은 JS를 사용하여 getMin 함수를 사용하여 스택을 구현하는 방법을 주로 소개합니다. 이제 특정 참조 값이 있으므로 필요한 친구들이 참조할 수 있습니다.

#🎜 🎜# 서문:

입사 확정했습니다~ 논리적으로 다음주 월요일에 정식 입사할 수 있을 것 같습니다. 하지만, 속으로는 항상 불안해요. 레벨이 너무 낮아서, 이제 시간이 있을 때 책도 더 읽고, 공부도 더 하는 게 좋을 것 같아요. 그래서 예전에 학교에서 샀던 책들을 꺼내서 읽어요. .. 모두 아주 고전적인 책들이지만, 취직하고 나서 거의 다 책장에 방치되어 먼지가 쌓이게 되었거든요. 공부하는 습관. 바쁘더라도 새로운 것을 배우기 위해 시간을 내야 합니다. 둘째, 열심히 일할 때 자신을 기록하고 싶습니다. 게으르고 싶을 때 "게으른 놈아, 빨리 배워라. 그렇지 않으면 과거에도, 앞으로도 열심히 일한 너 자신에게 후회하게 될 거야."라고 스스로에게 말할 수도 있습니다. , 잡담은 이제 본격적으로 시작하겠습니다~ 🎜#

　[제목] 특수 스택 구현 스택의 기본 기능 구현을 바탕으로 스택에서 가장 작은 요소를 반환하는 연산을 구현합니다.

[요구 사항] 1. pop, push, getMin 작업의 시간 복잡도는 O(1) 2. 설계된 스택 유형은 기존 스택 구조를 사용할 수 있습니다# 🎜 🎜# [아이디어] stackData와 stackMin을 정의합니다. stackData는 실제 데이터를 저장하는 데 사용되며 stackMin은 stackData에 최소값을 저장하는 데 사용됩니다. stackData와 stackMin 간의 데이터 동기화를 달성하기 위해 pop 및 push 메소드를 다시 작성하십시오.

[구현] 구현하는 방법은 2가지가 있는데 자세한 내용은 코드를 참고하세요.

         // 方法一 1 class MyStack {
    constructor() {
        this.stackData = [];
        this.stackMin = [];
    }
    push() {
        let args = arguments[0];
        if (typeof args === &#39;number&#39;) {
            //将新数据压入stackData栈中
            this.stackData.push(args);
            //判断是否将新数据压入stackMin栈中
            if (this.stackMin.length > 0) {
                //stackMin栈不空，需要判断当前数据是否小于等于stackMin的栈顶元素
                let top = this.getMin();
                if (args <= top) {
                    this.stackMin.push(args);
                }
            } else {
                //stackMin栈空，则压入
                this.stackMin.push(args);
            }
        }
    }
    pop() {
        if (this.stackMin.length === 0) {
            throw new Error(&#39;Stack is empty!&#39;);
        }
        let p = this.stackData.pop();
        let top = this.getMin();
        if (p === top) {
            this.stackMin.pop();
        }
        return p;
    }
    getMin() {
        if (this.stackMin.length === 0) {
            throw new Error(&#39;Stack is empty!&#39;);
        }
        let len = this.stackMin.length;
        return this.stackMin[len - 1];
    }
}
let s = new MyStack();
s.push(4);
s.push(2);
s.push(1);
console.log(s.getMin());
s.pop();
console.log(s.getMin());
s.pop();
s.pop();
s.pop();    //抛出异常

          //方法二 1 class MyStack {
    constructor() {
        this.stackData = [];
        this.stackMin = [];
    }
    push() {
        let args = arguments[0];
        if (typeof args === &#39;number&#39;) {
            //将新数据压入stackData栈中
            this.stackData.push(args);
            //判断是否将新数据压入stackMin栈中
            if (this.stackMin.length > 0) {
                //stackMin栈不空，需要判断当前数据是否小于等于stackMin的栈顶元素
                let top = this.getMin();
                if (args <= top) {
                    this.stackMin.push(args);
                } else {
                    this.stackMin.push(top);
                }
            } else {
                //stackMin栈空，则压入
                this.stackMin.push(args);
            }
        }
    }
    pop() {
        if (this.stackMin.length === 0) {
            throw new Error(&#39;Stack is empty!&#39;);
        }
        let p = this.stackData.pop();
        this.stackMin.pop();
        return p;
    }
    getMin() {
        if (this.stackMin.length === 0) {
            throw new Error(&#39;Stack is empty!&#39;);
        }
        let len = this.stackMin.length;
        return this.stackMin[len - 1];
    }
}
let s = new MyStack();
s.push(4);
s.push(2);
s.push(1);
console.log(s.getMin());
s.pop();
console.log(s.getMin());
s.pop();
s.pop();
// s.pop();    //抛出异常

후말:

이 글은 작성할 예정입니다. 시리즈로서 주요 참고자료는 Zuo Dashen의 "프로그래머 코드 인터뷰 가이드 - 유명 IT 기업의 알고리즘 및 데이터 구조 질문에 대한 최적의 솔루션"입니다. Zuo Dashen은 책에서 이를 구현하기 위해 JAVA를 사용합니다. JS를 사용하다 보면 거의 무의미하다는 생각이 항상 듭니다. 어쨌든 배우고 있는 중이라 JS의 작성 방법을 직접 구현해서 공유하는 것만으로도 계속해서 버틸 수 있는 원동력이 됩니다. 새내기들은 분명 어느정도 알겠지만 문제가 좀 있으니 전문가분들 웃으면서 조언 좀 해주시면 좋겠습니다~강상아미다~아니가도~고마워요~

JS를 사용하여 getMin 함수로 스택을 구현하는 방법

관련 기사