스택(Stack)은 데이터를 제한적으로 접근 할 수 있는 구조이다. 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조로 이러한 점은 큐(Queue)와 마찬가지이다. 하지만 큐(Queue)와 다른 점은 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터라는 점이다.
스택(Stack)은 큐(Queue)와 다르게 LIFO (Last-in, First-out) 또는 FILO (First-In, Last-Out)의 데이터 관리 방식을 따른다. 마치 책을 쌓는 것과 유사하다. 책을 순차적으로 바닥에서 쌓아 올리고 다시꺼낼 때 가장 나중에 올린책을 먼저 집어야 그 다음의 책을 꺼낼 수 있다. 대표적인 스택의 활용은 컴퓨터 내부의 프로세스 구조의 함수 동작 방식이다. 스택의 주요기능은 push()
, pop()
메서드처럼 데이터를 스택(Stack)에 넣거나 꺼내게 된다.
LIFO (Last-In, First-Out)
후입선출이라고 한다. 마지막에 넣은 데이터가 가장 먼저 나온다.FILO (First-In, Last-Out)
처음에 넣은 데이터가 가장 나중에 나온다.
스택(Stack)에 데이터를 넣는 것을 Push라고 하고 데이터를 꺼내는 것은 Pop이라고 한다. 스택 구조는 프로세스 실행 구조의 가장 기본이 된다. 함수 호출 시 프로세스 실행 구조를 스택과 비교해서 이해할 수 있다.
// 재귀 함수
function recursive(data) {
if (data < 0) {
console.log('ended');
} else {
console.log(data);
recursive(data - 1);
console.log('returned', data);
}
}
recursive(4);
스택(Stack)의 장점은 데이터 구조가 단순해서 구현하기가 쉽다. 그리고 데이터를 저장하거나 읽는 속도가 빠르다. 스택의 단점은 일반적인 스택 구현시 데이터의 최대 갯수를 미리 정해야 한다. Python의 경우 재귀함수는 1,000번까지만 호출이 가능하다. 이 뜻은 1,000번을 호출할 수 있는 공간을 미리 확보를 해두었다는 것과 같다. 즉, 데이터 저장 공간의 낭비가 발생할 수 있다.
스택은 단순하고 빠른 성능을 위해 사용되므로 보통 배열 구조를 활용해서 구현하는 것이 일반적이다. 이런 경우에는 앞에서 말한 단점이 있을 수 있다.
Javascript에서 스택(Stack)을 Class
로 구현하면 다음과 같다.
class Stack {
#array; // private
constructor(array = []) {
if (!Array.isArray(array)) {
throw new TypeError(`${array} is not an array.`);
}
this.#array = array;
}
push(value) {
return this.#array.push(value);
}
pop() {
return this.#array.pop();
}
entries() {
return [...this.#array];
}
}
const stack = new Stack([1, 2]);
console.log(stack.entries()); // [1, 2]
stack.push(3);
console.log(stack.entries()); // [1, 2, 3]
stack.pop();
console.log(stack.entries()); // [1, 2]
큐(Queue)와 스택(Stack)은 서로 유사하면서도 다른점을 갖고 있다. 두 자료구조는 비교적 쉽고 기초적인 자료구조이기 때문에 직접 구현해보고 시도해보면서 익숙해지는 것이 중요하다.
Velog - [자료구조] 큐(Queue)
Poiemaweb - 배열
이미지 출처 - 스택(Stack)의 구조