이 문서는 Google Cloud Translation API를 사용해 자동 번역되었습니다.
어떤 문서는 원문을 읽는게 나을 수도 있습니다.
스택은 데이터를 순서대로 저장할 수 있는 데이터 구조입니다. 스택의 맨 위에서만 책을 추가하거나 제거할 수 있는 책 더미처럼 생각할 수 있습니다.
스택은 종종 컴퓨터 프로그래밍에서 특정 순서로 데이터를 저장하는 데 사용됩니다. 예를 들어, 어떤 함수가 마지막으로 호출되었는지 추적해야 하는 프로그램을 작성할 때 스택을 사용합니다.
스택에서 수행할 수 있는 두 가지 주요 작업이 있습니다.
이러한 작업이 어떻게 작동하는지 보기 위해 예를 살펴보겠습니다.
정수 스택이 있다고 가정합니다. 숫자 1, 2, 3을 순서대로 스택에 푸시할 수 있습니다. 이제 스택은 다음과 같습니다.
삼
2
1
그런 다음 스택을 팝하면 3이 맨 위에서 제거되고 스택은 이제 다음과 같이 표시됩니다.
2
1
스택에 4를 푸시하면 다음과 같이 표시됩니다.
4
2
1
스택을 다시 팝하면 4가 제거되고 스택은 다음과 같이 표시됩니다.
2
1
보시다시피 스택은 항상 데이터를 특정 순서로 유지합니다. 마지막에 추가된 요소가 항상 가장 먼저 제거됩니다.
스택의 많은 응용 프로그램이 있습니다. 한 가지 예는 프로그래밍 언어용 컴파일러를 작성할 때입니다. 컴파일러는 올바른 코드를 생성할 수 있도록 호출되는 함수를 추적해야 합니다. 이를 위해 스택을 사용합니다.
또 다른 예는 웹 브라우저를 작성할 때입니다. 링크를 클릭하면 브라우저는 뒤로 버튼을 클릭할 때 해당 페이지로 돌아갈 수 있도록 사용자가 어느 페이지에 있었는지 추적해야 합니다. 이를 위해 스택을 사용합니다.
스택은 깊이 우선 검색과 같은 많은 알고리즘에도 사용됩니다.
스택을 구현하는 방법에는 여러 가지가 있습니다. 한 가지 방법은 배열을 사용하는 것입니다.
배열 끝에 요소를 추가하여 스택에 요소를 푸시할 수 있습니다. 배열의 끝에서 요소를 제거하여 스택에서 요소를 팝할 수 있습니다.
다음은 배열을 사용하여 스택을 구현하는 일부 코드입니다.
class Stack {
constructor() {
this.data = [];
}
push(element) {
this.data.push(element);
}
pop() {
return this.data.pop();
}
}
스택을 구현하는 또 다른 방법은 연결 목록을 사용하는 것입니다.
연결된 목록의 헤드에 요소를 추가하여 스택에 요소를 푸시할 수 있습니다. 연결된 목록의 헤드에서 요소를 제거하여 스택에서 요소를 팝할 수 있습니다.
다음은 연결된 목록을 사용하여 스택을 구현하는 일부 코드입니다.
class Stack {
constructor() {
this.head = null;
}
push(element) {
const node = {
data: element,
next: this.head
};
this.head = node;
}
pop() {
const node = this.head;
this.head = node.next;
return node.data;
}
}
푸시 및 팝 작업의 시간 복잡도는 O(1)입니다.
푸시 및 팝 작업의 공간 복잡도는 O(1)입니다.