스택(Stack)과 큐(Queue)는 프로그래밍이라는 개념이 탄생할 때 부터 있었던 가장 고전적인 자료구조 중 하나이다.
하지만 이 두 자료는 자바스크립트(JavaScript)에 내장되어 있지 않지만, 배열(Array)과 내장함수들을 사용하여 스택(Stack)과 큐(Queue)를 흉내낼 수는 있다.
대부분의 알고리즘 문제를 풀어야 할 경우 배열을 이용하더라도 통과하는 편이지만, 시간복잡도를 매우 세세하게 관리하거나 데이터의 양이 매우 큰 경우에는 이와 같은 방법으로는 통과할 수 없는 경우가 존재하기도 한다.
스택 (Stack)
- 스택은 자료구조형에 속한다.
- 먼저 들어간 자료가 나중에 나오는 후입선출 자료구조로 LIFO(Last In First Out) 라고도 부른다.
- 데이터를 입력하는
push()와 데이터를 제거하는pop()등의 작업을 할 수 있다. - ctrl+Z로 이전 작업을 취소하는 동작 등에서 사용된다.
method
- push : 스택의 맨 위에 아이템을 삽입한다
- pop : 스택 맨 위의 아이템을 제거하고 및 그 아이템을 반환한다
- contains : 해당 아이템이 스택에 존재하는지 확인한다
- size : 현재 스택에 있는 아이템의 총 개수를 반환한다
사용 예시
- 재귀 알고리즘
- 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
- 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
- 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
- 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
- 웹 브라우저 방문기록 (뒤로가기)
- 실행 취소 (undo)
- 역순 문자열 만들기
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
- 후위 표기법 계산
JavaScript 배열로 스택(Stack) 구현
export default class Stack {
constructor() {
// item들을 받을 배열 생성
this.items = [];
}
push(item) {
this.items.push(item);
}
pop() {
return this.items.pop();
}
peek() {
if (this.items.length === 0) {
return null;
}
// items 배열의 마지막 item만 가져와준다. pop()과 다르게 배열에서 아이템이 빠지는 것이 아닌 유지된 채로 마지막 값만 받아와줌
return this.items[this.items.length - 1];
}
getSize() {
return this.items.length;
}
isEmpty() {
return this.getSize() === 0;
}
}