Goal
- Stack에 대해 조사하고 완벽하게 설명할 수 있다.
- Javascript를 이용해서 Stack을 구현할 수 있다.
- Stack을 이용한 알고리즘 문제를 해결할 수 있다.
Stack이란 무엇인가?
- LIFO(Last-In First-Out) 의 구조를 가진 자료구조
- 순서가 보존되는 선형 데이터 구조
Stack의 사전적 정의는 'n.무더기', 'v.쌓다'입니다.
쌓여있는 자료구조라고 이해하면 쉽습니다.😄
이해를 돕기 위해 추상화를 해보겠습니다.
이렇게 맛있어 보이는 과일꼬치가 있다고 생각해봅시다.
이 것을 만들 때 어떤 순서대로 만들게 될까요?
귤 - 귤 - 키위 - 방울토마토 순으로 끼우게 되겠죠 !
그리고 먹을 때는 방울토마토 - 키위 - 귤 - 귤 순으로 먹게 될 것입니다.
이 과정이 Stack 과 정확하게 일치합니다 !
마지막에 넣은 방울토마토(Last-In)가
가장 처음으로 나오게 되겠죠!(First-Out)
이 것이 Stack 의 개념입니다.
Stack의 메서드
Stack의 대표적인 메서드로는 우리가 잘 아는 push(), pop()이 있고
pop()과 비슷하게 마지막 요소를 반환하나 제거하지는 않는peek()- 갯수를 확인할 수 있는
size() - Stack이 비어있을 때를 확인하는
isEmpty()
등으로 이루어져 있습니다.
그렇다면 Stack은 어디에 사용될까?
- PhotoShop, word 파일에서 뒤로가기(undo) =>
pop() - 웹 브라우저를 이용할 때 뒤로가기를 실행 =>
pop() - 역순 문자열 만들기
- a-p-p-l-e 순으로 넣게 되면
push()꺼낼 때 e-l-p-p-apop()
- a-p-p-l-e 순으로 넣게 되면
Stack을 만들어 보자!
Stack은 Array를 사용해 JavaScript의 내장 함수를 사용하면 쉽게 구현할 수 있습니다!
//stack.js
class Stack {
#array = [];
constructor() {}
push(value) {
this.#array.push(value);
}
pop() {
if (this.isEmpty()) throw new Error("[ERROR] 스택이 비어있어요!");
return this.#array.pop();
}
peek() {
// Stack이 비어있을 때 peek이나 pop을 하면 에러 반환
if (this.isEmpty()) throw new Error("[ERROR] 스택이 비어있어요!");
return this.#array[this.#array.length - 1];
}
size() {
return this.#array.length;
}
isEmpty() {
let result = false;
if (this.#array.length === 0) {
result = true;
}
return result;
}
}
그러나 사실 Stack은 배열을 사용하지 않아도 됩니다!
맨 마지막 값을 제외하고는 조회할 필요가 없기 때문이죠!
그럼 배열을 사용하지 않고 어떻게 구현할 수 있을까요?
이 부분은 Linked List를 공부한 후에 더 채워 넣도록 하겠습니다 😶🌫️
Stack을 이용한 알고리즘 문제 풀이
프로그래머스 알고리즘 풀이
