지금까지 자료 구조를 논할 때는 주로 자료 구조에 따라 다양한 연산의 성능이 어떻게 달라지는가에 초점을 맞췄다. 하지만 프로그래밍 지식 창고에 다양한 자료 구조를 쌓아 두면 보다 간단하고 읽기 쉬운 코드를 생성하는 데 도움이 된다.
스택과 큐는 제약을 갖는 배열이다. 이러한 제약 덕분에 두 자료 구조가 매우 간결해진다.
스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구다. 다양한 분야에서 사용해 뛰어난 알고리즘을 만들 수 있다.
스택이 데이터를 저장하는 방법은 배열과 같다. 단순히 원소들의 리스트지만 세 가지 제약이 있다.
스택의 끝을 위(top), 스택의 시작을 밑(bottom)이라고 부른다.
스택에 새로운 값을 삽입하는 것을 스택에 푸시한다고 하고, 스태그이 위에서 원소를 제거하는 것을 스택으로부터 팝한다고 한다.
스택 연산은 LIFO(Last In, First Out)이다. 즉, 스택에 푸시된 마지막 항목이 스택에서 팝될 첫 번째 항목이라는 의미다.
대부분의 프로그래밍 언어에는 스택이 내장 데이터 타입이나 클래스로 딸려 있지 않다. 직접 구현해야 한다.
class Stack {
constructor() {
this._data = [];
}
push(item) {
this._data.push(item);
}
pop() {
return this._data.pop();
}
read() {
return this._data[this._data.length - 1];
}
}
이 스택은 _data라는 배열에 데이터를 저장한다.
스택을 초기화하면 자동으로 빈 배열을 생성한다. 또한 스택에는 새 원소를 배열에 푸시하는 메서드, 원소를 팝하는 메서드, 원소를 읽는 메서드가 있다.
배열을 기반으로 Stack 클래스를 만들 보니 사용자가 배열과 상호작용하는 인터페이스가 제한적일 수 밖에 없다. 원래 배열은 어떤 인덱스든 정상적으로 읽을 수 있으나, 스택 인터페이스로 배열을 사용하면 마지막 항목만 읽고, 삽입하고, 삭제할 수 있다.
사실 스택은 꼭 배열로만 만들어야 하는 것은 아니다. LIFO 방식으로 동작하는 데이터 원소들의 리스트이기만 하면 된다. 그렇기 때문에 스택은 추상 데이터 타입에 속한다.