스택 개요
- 가장 기본적인 선형 자료구조 중 하나로 스택의 상단에서 새로운 요소의 삽입과 삭제가 발생합니다.
- 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 후입선출(LIFO) 방식으로 데이터를 처리하는 구조입니다.
- 스택은 맨 위에 있는 요소에만 접근할 수 있기 때문에 스택의 맨 위에 대한 포인터를 유지해야 합니다.
- 데이터를 저장하고 검색하는 데 사용됩니다.
스택 동작 원리
- push(item) : 새로운 항목을 스택의 top에 추가합니다.
- pop() : 스택의 맨 위에 있는 데이터를 제거하고 반환합니다.
- peek() : 스택의 맨 위에 있는 데이터를 반환하지만 제거하지 않습니다.
- isEmpty() : 스택이 비어있는지 확인합니다.
- size() : 스택의 크기를 반환합니다.
스택의 push 작업
- 요소를 스택에 푸시하기 전에 스택이 가득 찼는지 확인합니다.
- 스택이 가득차면 스택 오버플로가 발생하여 스택에 요소를 push할 수 없습니다.
- 그렇지 않으면 top(포인터) 값을 1씩 증가시킵니다.
스택의 pop 작업
- 스택에서 요소를 꺼내기 전에 스택이 비어있는지 확인합니다.
- 스택이 비어 있으면 스택 언더플로우가 발생하고 스택에서 요소를 제거할 수 없습니다.
- 그렇지 않으면 top 값을 1씩 감소하고 요소를 반환합니다.
스택 배열 코드 예시
class Stack {
constructor() {
this.items = []
}
size() {
return this.items.length
}
isEmpty() {
return this.size() === 0
}
push(el) {
this.items.push(el)
}
pop() {
if(this.isEmpty()) throw new Error("empyt stack")
return this.items.pop()
}
peek() {
if(this.isEmpty()) throw new Error("empyt stack")
return this.items[this.size() - 1]
}
}
스택 링크드리스트 코드 예시
class Node {
constructor(el) {
this.item = el
this.next = null
}
}
class Stack {
constructor() {
this.top = null
this.length = 0
}
size() {
return this.length
}
isEmpty() {
return this.size() === 0
}
push(el) {
const node = new Node(el)
node.next = this.top
this.top = node
this.length++
}
peek() {
if(this.isEmpty()) throw new Error("empty stack")
return this.top.item
}
pop() {
if(this.isEmpty()) throw new Error("empty stack")
const item = this.peek()
this.top = this.top.next
this.length--
return item
}
}
- class Node에서 next는 top에 있는 node를 넣어서 링크드 리스트로 만들어서 관리합니다.
- push일때는 node를 새로 생성하여 현재 top위치에 넣어줍니다.
- pop일때는 현재 top을 next에 있는 node로 넣어줍니다.
스택 시간 복잡도
스택 공간 복잡도
- O(n) 데이터 개수에 비례하여 메모리 공간이 필요합니다.
스택 장점
- 단순한 구조로 이해하기 쉽습니다.
- 데이터 개수와 무관하게 연산이 수행됩니다.
스택 단점
- LIFO라서 중간 요소에 직접 접근할 수 없습니다.
스택 활용
- 함수 호출 스택
- 괄호 매칭
- 백트래킹 알고리즘
- 재귀 함수 호출
- 웹 브라우저 방문 기록
