JavaScript 데이터 구조 및 알고리즘 stack_javascript 기술에 대한 자세한 설명

이전 글에서 블로그에서 소개한 목록은 가장 간단한 구조이지만, 좀 더 복잡한 구조를 다루려면 목록이 너무 단순해서 어떤 종류가 필요합니다. of 및 List는 스택과 비슷하지만 더 복잡한 데이터 구조입니다. 스택은 스택의 맨 위에서만 데이터를 추가하거나 삭제할 수 있으므로 효율적인 데이터 구조이므로 이 작업을 빠르고 쉽게 구현할 수 있습니다.

1: 스택 작업.

스택은 특별한 종류의 목록입니다. 스택의 요소는 스택의 맨 위에 있는 목록의 한쪽 끝을 통해서만 액세스할 수 있습니다. 예를 들어, 식당에서 설거지를 할 때 상판만 먼저 씻을 수 있습니다. 접시를 씻은 후에는 접시 더미 꼭대기까지만 나사로 고정할 수 있습니다. 스택은 LIFO(후입선출)라는 데이터 구조입니다.

스택은 후입선출 특성을 가지므로 스택의 맨 위에 있지 않은 요소에는 접근할 수 없습니다. 스택의 맨 아래에 있는 요소를 얻으려면 위의 요소에 접근해야 합니다. 먼저 제거되었습니다. 스택에서 수행할 수 있는 두 가지 주요 작업은 요소를 스택에 푸시하는 것과 스택에서 요소를 팝하는 것입니다. push() 메서드를 사용하여 스택에 푸시하고 pop() 메서드를 사용하여 스택에서 튀어나올 수 있습니다. pop() 메서드는 스택 맨 위에 있는 요소에 액세스할 수 있지만 이 메서드를 호출한 후에는 스택 맨 위에 있는 요소가 스택에서 영구적으로 삭제됩니다. 일반적으로 사용되는 또 다른 방법은 스택의 최상위 요소를 삭제하지 않고 반환하는 peek()입니다.

스택에 push하고 pop하는 실제 다이어그램은 다음과 같습니다.

push(), pop() 및 peek()는 스택의 세 가지 주요 메서드이지만 스택에는 다른 메서드와 속성이 있습니다. 다음과 같습니다:

clear(): 스택의 모든 요소를 ​​지웁니다.

length(): 스택의 요소 수를 기록합니다.

2: 스택 구현은 다음과 같습니다.

다음과 같이 스택 클래스의 메서드를 구현하는 것으로 시작할 수 있습니다.

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

함수 스택() {
This.dataStore = [];
This.top = 0;
}

위와 같이 dataStore는 스택의 모든 요소를 ​​저장합니다. top 변수는 스택의 맨 위 위치를 기록하며 0으로 초기화됩니다. 이는 요소가 스택에 푸시되면 스택의 맨 위에 해당하는 배열의 시작 위치가 0임을 의미합니다. 그에 따라 변수 값이 변경됩니다.

또한 push(), pop(), peek(),clear(), length() 메소드도 있습니다.

1. Push() 메서드; 새로운 요소를 스택에 밀어넣을 때 배열의 변수 top에 해당하는 위치에 저장한 후 다음 요소를 가리키도록 top 값을 1 증가시킵니다. 배열에서의 위치. 다음 코드:

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

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

2. pop() 메서드는 push() 메서드와 반대입니다. -- 스택의 최상위 요소를 반환하고 최상위 값을 1씩 감소시킵니다. 다음 코드:

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

함수 팝(){
         return this.dataStore[--this.top];
}

3. peek() 메서드는 스택의 최상위 요소인 배열의 최상위 위치에 있는 요소를 반환합니다.

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

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

4. length() 메서드 스택에 요소가 몇 개 있는지 알아야 하는 경우가 있습니다. 다음 코드와 같이 top 변수의 값을 반환하여 스택에 있는 요소 수를 반환할 수 있습니다.

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

함수 길이(){

           return this.top;
}


5. Clear(); 때로는 스택을 지우고 싶을 때 다음 코드를 사용하여 변수 top 값을 0으로 설정합니다.

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

함수 클리어() {

this.top = 0;

}

아래의 모든 코드:

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

함수 스택() {
This.dataStore = [];
This.top = 0;
}

Stack.prototype = {
 
//새 요소를 스택에 푸시
푸시: 함수(요소) {
This.dataStore[this.top] = 요소;
},
// 스택의 최상위 요소에 액세스하면 스택의 최상위 요소가 영구적으로 삭제됩니다.
팝: 함수(){
          return this.dataStore[--this.top];
},
// 배열의 최상위 1번째 위치에 있는 요소, 즉 스택의 최상위 요소를 반환합니다
엿보기: 함수(){
          return this.dataStore[this.top - 1];
},
//스택에 저장된 요소 수
길이: 함수(){
         return this.top;
},
//스택 지우기
; 지우기: 함수(){
This.top = 0;
}
};

데모 예시는 다음과 같습니다.

var stack = new Stack();
stack.push("a");
stack.push("b");
stack.push("c");
console.log(stack.length()); // 3
console.log(stack.peek()); // c

var popped = stack.pop();
console.log(팝업); //c

console.log(stack.peek()) //b

stack.push("d");

console.log(stack.peek()) //d

스택.클리어();

console.log(stack.length()) // 0

console.log(stack.peek()) // 정의되지 않음

아래에서는 5와 같은 계승 함수의 재귀적 정의를 구현할 수 있습니다. 5의 계승! = 5*4*3*2*1

다음 코드:

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

함수 사실(n) {
var s = new Stack();
; 동안(n > 1) {
s.push(n--);
}
var 제품 = 1;
While(s.length() > 0) {
제품 *= s.pop();
}
반품상품입니다
}
console.log(fact(5));

위 코드의 의미는 다음과 같습니다. 먼저 숫자 5를 함수에 전달하고 while 루프를 사용하고 스택을 사용하여 push() 함수를 스택에 푸시한 후 변수 n이 다음과 같을 때까지 매번 1씩 감소시킵니다. 1보다 작습니다. 그런 다음 변수 product를 정의합니다. 스택의 length() 메서드를 사용하여 0보다 큰지 확인하고 매번 product* = s.pop()을 실행합니다. pop() 메서드는 스택의 최상위 요소를 반환하고 삭제합니다. 스택의 요소입니다. 따라서 실행될 때마다 s.length()