JavaScript의 스택 데이터 구조 이해—JavaScript는 이를 어떻게 사용합니까?

반응형

나는 스택이라는 단어를 처음 봤을 때 이해하기 쉬웠던 것 같아. 그런데 자바스크립트를 배우다가 동기식, 비동기식, 콜스택을 접했을 때 조금 혼란스러웠습니다.

저와 같은 혼란스러운 분들을 위해 이 글을 쓰고 있는데, 이 글을 마치면 여러분이 스택 데이터 구조와 자바스크립트가 어떻게 사용하는지에 대해 더 잘 이해할 수 있기를 바랍니다.

개요

이 글에서는 스택 데이터 구조, 자바스크립트 동기/비동기 및 콜 스택이 어떤 형태인지, 어떻게 사용되는지 알아보겠습니다.

JavaScript에 익숙하다면, 매일 사용하는 JavaScript Runtime의 작동 방식에 대한 새로운 통찰력을 얻을 수 있기를 바랍니다.

 

그리고 만약 당신이 자바스크립트를 상대적으로 처음이라면, 바라건대, 이것은 당신이 자바스크립트의 작동 방식을 이해하는데 도움이 될 것이다.

>> 데이터 구조에서 '더 스택'은 무엇입니까?

스택의 데이터 구조는 스택링과 더미의 사전적 정의와 같습니다. 쉽게 말해 바닥이 막힌 박스를 생각하면 됩니다. 밑이 막혀서 위에 물건을 놓고 위에서 꺼낼 수밖에 없다. 이런 구조 때문에 먼저 들어온 물건은 나중에 나갈 수 있고, 나중에 들어온 물건은 먼저 나갈 수 있다. 스택은 LIFO(Last-In-First-Out) 또는 FILO(First-In-Last-Out)를 따르는 선형 데이터 구조입니다.

> 스택의 작업

 

위의 그림에서 볼 수 있듯이,
스택은 LIFO(또는 FILO) 패턴에서 작동합니다. 스택이 아래에서 위로 채워지고 새 요소가 위로 이동합니다.

스택에서 요소를 제거하면 상자의 아래쪽이 차단되어 있으므로(맨 위만 차단되지 않음) 첫 번째 요소가 마지막으로 제거됩니다.

위의 경우 1이 먼저 입력되므로 다른 요소가 모두 제거된 후에야 마지막으로 제거됩니다.

> 표준 스택 작업

다음은 스택에 구현된 몇 가지 일반적인 연산입니다.

 

• push(): 스택에 요소를 추가하려는 경우 이 작업을 push라고 합니다(스택이 가득 차지 않은 경우에만).
• pop(): 스택에서 요소를 제거하려는 작업을 pop이라고 합니다. (스택이 비어 있지 않은 경우에만)
• top/peek(): 추가 또는 삭제하지 않고 스택에서 최상위 요소를 반환합니다.
• 카운트다운: 스택의 총 요소 수를 반환합니다.
• 변경사항: 지정된 위치에서 요소를 변경합니다.
• 화면표시: 스택의 모든 요소를 인쇄합니다.
• isEmpty/isFull(): 스택이 비어 있는지 여부/스택이 가득 찼는지 여부를 결정합니다.

또한 Stack은 가득 차면 Overflow 상태이고 비어 있으면 Underflow 상태라고 합니다.

> 스택의 구현

스택은 어레이 또는 링크된 목록을 사용하여 쉽게 구현할 수 있습니다. 배열은 빠르지만 크기가 제한되어 있으며 링크된 목록은 할당, 링크, 링크 해제 및 할당 해제를 위해 오버헤드가 필요하지만 크기가 제한되지는 않습니다. 이 글에서는 배열을 사용하여 스택을 구현할 것입니다.

스택의 배열 구현
이것은 배열을 사용하여 형성됩니다. 배열 데이터 구조를 사용하여 각 작업을 스택에서 구현하는 방법에 대해 살펴보겠습니다.

 

예를들면
스택이라는 변수가 있는데, 이것은 배열입니다. 스택의 한도가 5라고 가정해봅시다.

• array.messages 메서드
• 스택이 가득 찼는지 확인합니다.
• 스택이 가득 차면 오버플로 오류를 인쇄하고 프로그램을 종료합니다.
• 스택이 가득 차지 않은 경우 맨 위를 증분하고 요소를 추가합니다.

 

2. array.popsecm 메서드

• 스택이 비어 있는지 확인합니다.
• 스택이 비어 있으면 언더플로 오류를 출력하고 프로그램을 종료합니다.
• 스택이 비어 있지 않으면 맨 위에 있는 요소를 인쇄하고 맨 위에 있는 요소를 줄입니다.

3. array.length 속성

 

JavaScript array.length 속성을 사용하면 다른 스택 연산자와 동일한 결과를 얻을 수 있습니다.

> 응용 프로그램

• 문자열 반전:

스택의 각 문자를 하나씩 스택에 삽입합니다. 따라서 String의 첫 번째 문자는 Stack의 맨 아래에 있고 String의 마지막 문자는 Stack의 맨 위에 있습니다. 스택에서 pop 작업을 수행한 후, 우리는 역순으로 문자열을 받습니다.

 

• UNDO/REDO —

편집자는 실행 취소 및 재실행 기능을 구현하는 데 이 방법을 사용할 수 있습니다. 실행 취소하려면 pop()을 사용하여 마지막 변경 내용을 제거하십시오.

• 역추적:

역추적은 최적화 문제를 해결하는 데 사용되는 재귀 알고리즘이다.

• 메모리 관리:

 

메모리 관리는 운영 체제의 중요한 기능입니다. 스택은 메모리 관리와 관련해서도 주요 역할을 담당합니다.

• 함수 호출 —

프로그래밍에서 한 함수에서 다른 함수로 호출할 때마다. 호출 함수의 주소가 스택에 저장됩니다. (call stack이라고 함) 그러므로 호출된 함수가 종료되면 프로그램 제어는 스택에 저장된 주소의 도움으로 호출 함수로 다시 이동합니다.

따라서 스택은 다른 함수에서 함수 호출에 있어 주요 역할을 합니다.

>> 자바스크립트에서 어떻게 사용되나요?

 

자바스크립트는 단일 스레드 단일 프로그래밍 언어이며, 이는 한 번에 하나의 작업 또는 코드 조각을 처리할 수 있음을 의미한다. 큐는 단일 호출 스택을 가지고 있으며 힙과 같은 다른 부분과 함께 자바스크립트 동시성 모델을 구성한다.

자바스크립트 엔진(Goggle의 V8 엔진)은 다음의 두 가지 주요 구성 요소로 구성된다.

• 메모리 힙 — 여기서 메모리 할당이 발생합니다(예: 변수, 함수 등).
• 스택 호출 — 코드가 LIFO 규칙에 따라 실행될 때 스택 프레임이 추가되고 삭제되며, 호출 스택의 각 항목을 스택 프레임이라고 합니다.

> 동기/비동기 기능

 

위에서 언급했듯이 자바스크립트는 단일 스레드 프로그래밍 언어이며, 이는 단일 콜 스택을 가지고 있다는 것을 의미한다. 그러므로 그것은 한 번에 한 가지 일을 할 수 있습니다.

그럼 짧은 시간 안에 해야 할 일이 많으면 어떻게 되는 건가요?

예를 들어, 브라우저가 복잡한 이미지를 처리해야 한다고 상상해 보십시오. 브라우저가 이미지를 처리하는 동안 다른 작업은 완료될 때까지 기다려야 합니다. 그리고 그것은 문제만이 아니다. 콜 스택이 작업을 완료하는 데 시간이 오래 걸릴 경우 브라우저가 응답을 중지한 후 브라우저를 중지(닫기)하려면 에러 메시지를 보냅니다.

우리는 이 문제를 어떻게 해결할 수 있을까요?

답은 비동기 콜백 함수를 사용하는 것입니다.
다시 말해, 코드 일부를 (동기적으로) 실행하고 나중에 (비동기적으로) 실행할 콜백을 제공합니다.

 

비동기 콜백은 즉시가 아닌 특정 시점에 실행되므로 console.log와 같은 동기 함수와 달리 콜 스택에 직접 푸시할 필요가 없다. 그러나 콜 스택이 아니라면 이러한 콜백 기능은 누가 관리합니까?

당신은 런타임 장에서 답을 찾을 수 있을 것이다.

> 호출 스택

기본적으로 우리가 어디에 있는지 함수 호출을 기록하는 데이터 구조입니다. 함수를 호출하여 실행시키면 첫 번째 함수를 스택 위로 밀어넣고, 함수에서 돌아오면 스택 위에서 튀어나온다.

예를 들어보자. 다음 코드를 살펴보십시오.

 

이 코드를 실행하기 전에 스택 프레임은 호출 스택에 존재하지 않습니다. 위의 코드에서는 console.log(bar(6)가 먼저 호출되고 첫 번째 스택 프레임이 됩니다.

다른 스택 프레임을 단계별로 살펴보겠습니다.

• 먼저 console.log(bar(6)를 호출합니다.
• 함수 막대로 이동한 다음 foo (6 * 3)인 foo(x * y)를 반환합니다.
• foo 함수로 이동한 다음 5 * 18 + 10인 a * b * 10을 반환합니다.
• 콘솔에 100을 기록합니다.
• 그러면 콜 스택 6 박스는 빈 콜 스택 박스가 됩니다.

 

> 스택 오버플로

스택 오버플로우는 스택이 오버플로되었음을 의미합니다. 특정 작업을 수행하는 동안 팝 없이 계속 누르면 제한된 호출 스택 공간의 크기를 초과하게 되는데, 이를 스택 오버플로라고 합니다.

예를 들어보자. 다음 코드를 살펴보십시오.

콜 스택을 보기 전에 콜 스택이 어떻게 생겼을지 추측해 보겠습니다.

 

• 먼저 foo() 함수를 호출합니다.
• foo() 함수는 foo() 함수 자체를 반환합니다.
• 그리고 foo() 함수는 다시 foo() 함수를 반환합니다.
• 계속해서….

foo() 함수는 재귀적이며 끝점 없이 자신을 계속 호출한다. 따라서 실행 단계마다 동일한 함수가 콜 스택에 계속 추가됩니다.

따라서 콜 스택 상자는 다음과 같이 표시됩니다.

어떤 시점에서, 호출 스택은 호출 스택의 실제 크기를 초과합니다. Uncaught RangeError: 최대 호출 스택 크기를 초과했습니다.와 같은 오류가 발생합니다.

 

> 런타임

• Web API — 웹 API는 JasaScript 엔진이 아닙니다. 브라우저에서 제공하는 API입니다. 콜 스택에서 실행되는 비동기 함수는 웹 API를 호출하고 웹 API는 이를 콜백 큐에 밀어 넣는다.
• 콜백 대기열 — 비동기적으로 실행된 콜백 함수가 저장되는 영역입니다. (큐: 데이터 구조 중 하나는 선입선출 FIFO 규칙을 따릅니다.)
• 이벤트 루프 - 콜 스택 및 콜백 대기열의 상태를 확인합니다. 콜 스택이 비어 있으면 콜백 대기열의 첫 번째 콜백을 콜 스택으로 밀어 넣습니다. 이러한 반복적인 행동을 틱이라고 합니다.

런타임 단계 —

• JavaScript 엔진(V8)에서 코드가 실행되면 콜 스택에 누적됩니다.
• 스택의 FILO/LIFO 규칙에 따르면 마지막 함수가 먼저 실행됩니다.
• 콜 스택에 축적된 모든 함수가 실행됩니다.
• 비동기 함수가 실행되면 웹 API가 호출됩니다.
• 웹 API는 비동기 함수의 콜백 함수를 콜백 대기열에 밀어 넣는다.
• 콜 스택이 비어 있으면 이벤트 루프는 콜백 큐의 첫 번째 콜백을 콜 스택으로 푸시합니다.

 

자바스크립트는 단일 스레드 프로그래밍 언어이다. 따라서 한 번에 하나의 작업을 처리할 수 있을 뿐만 아니라 하나의 호출 스택만 가지고 있습니다. 하지만 웹 API, 콜백 큐, 이벤트 루프 덕분에 멀티 스레드처럼 보입니다.

>> 결론

제가 이 글을 쓰면서 스택에 대한 제 지식도 정리할 수 있었고, 불분명한 부분들도 발견할 수 있었습니다. 이 문서가 스택, 콜 스택, Sync/Async 함수 및 JavaScript Runtime에 대한 이해를 높이는 데 도움이 되었기를 바랍니다.

이 기사의 요점은 다음과 같습니다.

• 스택은 FILO/LIFO 규칙을 따릅니다.
• push()/pop() 작업을 사용하여 스택의 요소 추가/삭제.
• 자바스크립트는 단일 스레드 프로그래밍 언어이다. 즉, JS는 한 번에 하나의 작업을 처리할 수 있으며 하나의 호출 스택을 가지고 있습니다.
• 비동기 함수를 사용하면 JS 단일 콜 스택의 문제를 해결할 수 있습니다.
• Web API, Callback Queue, Event Loop은 비동기 기능을 처리합니다. 호출 스택이 비어 있으면 첫 번째 비동기 함수를 호출 스택에 밀어 넣습니다.

 

> 참조: