JavaScript의 데이터 구조 및 알고리즘 (1): stack_javascript 기술

서문

데이터 구조 및 알고리즘 자바스크립트는 자바스크립트 언어를 사용하여 흔히 사용되는 데이터 구조를 비교적 간단하게 설명하는 책으로, 책에 나오는 많은 예가 흔히 볼 수 있는 면접 질문에서 나온 것입니다. 시대에 발맞춰서, 그런데 아마추어로 보고 녹화해봤습니다

git 코드 다운로드: https://github.com/JsAaron/data_structure.git

스택 구조

특수 목록, 스택의 요소는 목록의 한쪽 끝인 스택 상단을 통해서만 액세스할 수 있습니다

후입선출(LIFO, 후입선출) 데이터 구조

Javascript는 push와 pop이라는 작동 가능한 메소드를 제공하지만 pop은 스택의 데이터를 제거합니다

스택을 구현하는 구현 클래스

배열을 사용하는 기본 데이터 구조

pop은 스택에 있는 데이터를 삭제하기 때문에 peek 검색 방식을 구현해야 합니다

클리어 청소 방법 구현

스택 길이의 총 요소 수 찾기

아직 비어 있는 요소가 있는지 확인

코드 복사 코드는 다음과 같습니다.

함수 스택(){
This.dataStore = []
This.top = 0;
This.push = 푸시
디스.팝 =팝
This.peek = 엿보기
This.length = 길이;
}

함수 푸시(요소){
This.dataStore[this.top] = 요소;
}

함수 peek(요소){
return this.dataStore[this.top-1];
}

팝업() 기능{
return this.dataStore[--this.top];
}

함수 클리어(){
This.top = 0
}

함수 길이(){
반환 this.top
}

회문

회문이란 앞뒤가 동일한 단어, 배열, 구를 말합니다. 12321.abcba

회문의 가장 간단한 아이디어는 요소가 반전되어 원래 요소와 같으면 회문이라는 의미입니다

이 스택 클래스를 사용하여 여기에서 작업할 수 있습니다

코드 복사 코드는 다음과 같습니다.

function isPalindrome(단어) {
var s = 새로운 스택()
for (var i = 0; i s.push(단어[i])
}
var rword = "";
while (s.length() > 0) {
         rword = s.pop();
}
If (단어 == r단어) {
        true를 반환합니다.
} 그 밖의 {
         false를 반환합니다.
}
}

isPalindrome("aarra") //false
isPalindrome("aaraa") //true

이 isPalindrome 함수를 보세요. 실제로 Stack 클래스를 호출한 다음 분해된 각 단위에 전달된 단어 요소를 스택에 푸시합니다. 즉, 후입선출 원칙을 사용합니다. 이 요소를 팝 방식으로 분해하고 최종적으로 조립 전과 후를 비교하면 회문입니다

재귀

재귀를 사용하여 계승 알고리즘 구현

5! = 5*4*3*2*1 = 120

재귀 사용

코드 복사 코드는 다음과 같습니다.

함수 계승(n) {
If (n === 0) {
1을 반환;
} 그 밖의 {
          n * 계승(n - 1)을 반환합니다.
}
}

스택 작업 사용

코드 복사 코드는 다음과 같습니다.

함수 사실(n) {
var s = 새로운 스택()
동안(n > 1) {
              //[5,4,3,2]
s.push(n--);
}
var 제품 = 1;
while (s.length() > 0) {
제품 *= s.pop();
}
반품상품입니다
}

사실(5) //120

while을 통해 n = 5를 스택에 점진적으로 푸시한 후 루프를 통과하거나 스택의 후입선출 원리에 따라 맨 앞의 것을 꺼내어 팝 방식으로 제품과 함께 쌓습니다.