[Kotlin/자료구조] Stack과 Queue에 대하여

Stack(스택)과 Queue(큐)는 선형 자료구조 중 하나이다. 이에 대해서 알아보고 Kotlin에서는 어떻게 사용하는지 알아보는 포스트이다.

1. Definition

Stack(스택)의 정의

Stack은 삽입과 삭제가 한쪽 끝에서 이루어지는, 순서가 매겨진 리스트이다.

LIFO(Last In First Out, 후입 선출) 혹은 FILO(First In Last Out, 선입 후출)의 형태이다.

Stack의 구조

위 그림과 같이 데이터를 삽입할 때 마다 바닥에 순서대로 쌓이며 꺼낼 때에는 가장 나중에 들어온 데이터가 꺼내진다.

Stack에서의 삽입과 삭제의 행위를 각각 push(삽입)와 pop(삭제)이라고 부른다.

 

Java의 단일 클래스로 Stack<E> 클래스(extends Vector<E>)가 존재하며 Kotlin에서 사용할 경우 java.util.*의 import가 필요하다.

 

Queue(큐)의 정의

Queue는 데이터의 삽입이 한쪽 끝(뒤, rear)에서 이루어지고, 삭제는 다른 쪽 끝(앞, front)에서 이루어지는 정렬된 리스트이다.

FIFO(First In First Out, 선입 선출) 혹은 LILO(Last In Last Out, 후입 후출)의 형태이다.

Queue의 구조

위 그림과 같이 데이터를 삽입할 때 한쪽 끝(해당 그림은 앞이라고 볼 수 있겠다)에서 이루어지며, 꺼낼 때 다른 한쪽 끝(해당 그림은 뒤라고 볼 수 있겠다)에서 이루어진다.

Queue에서의 삽입과 삭제의 행위를 각각 enqueue(삽입), dequeue(삭제)라고 부른다.

 

Queue는 Stack과 다르게 interface로 존재하며 생성 시에 LinkedList와 같은 자료구조와 함께 사용된다.

또한 Kotlin에서는 enqueue()와 dequeue() 함수가 그대로 존재하지 않고 offer()과 poll() 함수가 존재한다.

 

---

2. Method Summary

유틸 클래스(java.util.*)에 정의되어 있는 Stack과 Queue의 Method들에 대하여 소개하겠다.

Stack의 Method

Modifier and Type	Method	Description
boolean	empty()	Stack이 비어있다면 true, 아니면 false를 반환한다.
E	peek()	Stack에서 제거하지 않고 스택의 최상단(맨 위)에 있는 객체를 확인한다.
E	pop()	Stack의 최상단에 있는 객체를 제거하고 해당 객체를 return한다.
E	push(E item)	Stack에 최상단 항목으로 삽입한다.
int	serach(Object o)	Object를 Stack에서 찾는 method로 최상단 객체를 1로 하여(1-based-position) 위치(position)를 찾아주며, 객체가 없다면 -1을 return한다.

Queue의 Method

Modifier and Type	Method	Description
boolean	add(E e)	Queue에 객체를 추가한다. Queue의 남아 있는 space가 없을 경우 exception을 throw한다.
E	element()	Queue에 가장 먼저 들어간 객체를 return한다.
boolean	offer(E e)	Queue에 객체를 추가한다. 이때는 exception을 발생시키지 않고 성공 여부에 대해 return한다.
E	peek()	Queue에 가장 먼저 들어간 객체를 제거하지 않고 확인한다.
E	poll()	Queue에 가장 먼저 들어간 객체를 제거하고 해당 객체를 return한다. 이때 queue가 비어 있다면 null을 return한다.
E	remove()	Queue에 가장 먼저 들어간 객체를 제거하고 해당 객체를 return한다. 이때 queue가 비어있다면 exception을 throw한다.

---

3. Reference

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Stack.html

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html