[Kotlin] 스택 - Stack
🔷 스택(Stack)이란?
스택(Stack)은 쌓아 올린다는 의미이다.
선형 리스트의 한쪽에서만 자료의 입력과 출력이 가능한 자료구조이다.
따라서 선형 리스트의 끝 부분에 대한 정보를 가지고 있는 변수가 필요하다.
이런 스택의 구조를 후입선출 (LIFO, Last-In First-Out)구조 라고 한다.
🔹스택의 끝 부분 : top
스택은 정해진 방향으로만 데이터를 삽입, 출력이 가능하다.
통 속에 물건을 집어넣거나, 접시를 쌓아올리는 형식과 유사하다.
스택을 사용하기 위해서는 데이터가 이동하는 위치 정보가 필요하며, 주로 변수명으로 top을 사용한다.
top은 가장 최근에 삽입된 자료를 가르키며, 새 자료는 top이 가르키는 자료 위에 쌓인다.
삭제 또한 top이 가리키는 자료부터 순서대로 진행된다.
🔹push() : top을 통해 스택에 데이터를 삽입하는 연산
🔹pop() : top을 통해 스택에 데이터를 삭제하는 연산
🔹후입선출 (LIFO, Last-In First-Out)
스택은 한쪽 끝(top)에서만 데이터의 삽입과 삭제 작업이 진행되며, 시간 순서에 따라 데이터가 쌓인다.
따라서 가장 나중에 들어온 원소가 가장 먼저 삭제되는 특성을 가진다.
이런 스택의 구조를 후입선출(LIFO : Last-Int First-Out)를 가지게 된다.
🔷 stack overflow
스택이 비어있을 경우 top은 -1의 값을 가진다.
비어있는 스택(top==-1)에서 원소를 추출하려고 할 때 stack underflow라고 한다.
지정한 스택의 최대크기를 넘어설 경우 stack overflow가 발생한다.
유명한 개발 사이트 stack overflow의 유래이다.
🔷 스택 사용법
Stack -> 스택 초기 설정
push -> 스택에 데이터 삽입 : 가장 위에 삽입
add -> 스택에 데이터 삽입 : 정해진 위치에 삽입 / 변경
pop -> 스택에 데이터 반환 및 삭제
peek -> 현재 top 위치 반환
size -> 스택의 크기 반환
stack[i] -> 스택의 i번째 원소 반환
search -> 원소의 위치를 위에서부터 탐색하여 반환 : Index 번호 아님!
isEmpty | isNotEmpty -> 스택의 원소 존재 유무 확인
🔹Import
kotlin에서는 자체적으로 Stack을 제공하지 않으므로 직접 구현하거나 java에서 호출한다.
현 게시글에서는 java에서 호출하는 방식으로 작성한다.
java.util 에서 전체(*)혹은 스택(Stack)만 import하여 사용한다.
import java.util.*
import java.util.Stack🔹Stack
스택 초기 설정
val stack : Stack<DataType> = Stack<DataType>()🔹push
스택에 데이터 삽입
가장 위(top 위치)에 원소를 삽입한다.
stack.push(value)🔹add
스택에 데이터 삽입
지정한 위치에 원소를 삽입한다.
stack.add(index, value)🔹pop
스택에 데이터 반환 및 삭제
빈 스택에 사용할 경우 에러 발생 : Exception in thread "main" java.util.EmptyStackException
stack.pop()🔹peek
현재 top 위치 반환
빈 스택에 사용할 경우 에러 발생 : Exception in thread "main" java.util.EmptyStackException
stack.peek()🔹size
스택의 크기 반환
stack.size🔹stack[i]
스택의 i번째 원소 반환
stack[index]🔹search
원소의 위치를 위에서부터 탐색하여 반환
Index 번호는 아래에서부터로 혼동하지 않도록 주의한다.
만약, 원소가 존재하지 않을 경우 -1을 반환한다.
stack.search(value)🔹isEmpty | isNotEmpty
스택의 원소 존재 유무 확인
stack.isEmpty()
stack.isNotEmpty()✨ isEmpty()과 isNotEmpty()의 출력 차이
isEmpty(): 빈 스택일 경우 true
isNotEmpty() : 빈 스택이 아닐 경우 true
🔷 스택의 모든 원소 삭제
🔹isNotEmpty() + pop()
스택이 비어있지 않을 경우 반복
스택의 원소를 삭제
while(stack.isNotEmpty()){
stack.pop()
}