시작하기

지난 번에 이어 이번에 stack과 queue를 알아보자. 해당 개념들은 과거에 한번씩 다뤘었기에 개념보단 kotlin에서의 실 활용에 초점을 맞춰본다.

Stack

stack은 재귀적인 함수나, 알고리즘에서 자주 사용된다. LIFO(last in first out)의 성질을 가진 자료구조이며 삽입, 삭제는 O(1), 검색에 O(n)이 걸린다.

in kotlin

import java.util.*

val s = Stack<Int>()
s.push(3)
s.push(4)
s.push(5)
println(s) // [3,4,5]
println(s.peek()) // 5
println(s.pop()) // 5
println(s) // [3,4]

• push : stack의 맨 위에 값을 넣는다
• pop : stack의 맨 위에서 값을 뺀다
• peek : stack의 맨 위 값을 확인한다.

활용

문자열 역순 출력 등 뒤집기

Queue

Queue는 FIFO(First in First Out)이라는 Stack과는 다른 성질을 지녔다. 일반적으로 줄서기 라고 생각하면 이해가 편하다. 삽입과 삭제에는 O(1)이, 검색에는 O(n)이 걸린다.

in kotlin

kotlin에서 queue는 interface 일 뿐 클래스가 아니다. 따라서 LinkedList를 통해 initialize 해준다.

import java.util.*

val q: Queue<Int> = LinkedList()

q.add(1) // 에러 발생시 Throw Exception
q.offer(2) // 

q.element() // 1 에러 발생 시 Throw Exception
q.peek() // 1 , 가장 앞에 있는 값 확인, 에러 발생시 null return

q.remove() // 1, 에러 발생시 Throw Exception
q.poll() // 2, 에러 발생시 null return

위에서 보이듯 두 method씩 각각 같은 역할을 하나 에러 발생시의 처리가 다르다. 여기서 add는 원래 capacity가 부족할 경우 exception을 발생시키나, LinkedList()를 통해 만든 queue의 경우 해당 이슈는 발생할 가능성이 거의 없다.

활용

프로세스의 스케줄링 (먼저 들어온 것 부터), 줄서기, BFS 등