[JAVA] Stack이란?

Stack이란?

Stack은 LIFO(Last-in, First-out) 의 특성을 가지고 있는 자료구조이다.

즉, 나중에 들어온 것이 먼저 나가는, 바닥부터 차곡차곡 쌓고 제일 위를 꺼내는 특성을 가지고 있다!

Stack의 시간 복잡도는 다음과 같다.

삽입(push)	O(1)
삭제(pop)	O(1)
읽기(peek)	O(1)
탐색(search)	O(n)

 

Java로 코테에서 Stack 활용하기

java에서는 Stack클래스를 제공하고 있다.

하지만 오라클 공식 문서에 따르면 Stack 클래스 보다는 ArrayDeque를 활용하는 것을 추천한다.

(https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/ArrayDeque.html)

This class is likely to be faster than Stack when used as a stack,
and faster than LinkedList when used as a queue.

Deque<Integer> stack = new ArrayDeque<Integer>();

코테에서는 이와 같이 선언하고 활용하면 된다!

 

Method

void push(E e) : 가장 top에 element 삽입

E pop() : 가장 top에 있는 element를 remove하고 반환

E peek() : 가장 top에 있는 element 반환

boolean contains(Object o) : 해당 element 포함 여부 반환

int size() : element의 수 반환

boolean isEmpty() : element가 없는지 여부 반환

stack으로 활용하기 위해서는 간단하게 이 정도만 알면 된다. 추가적으로 알고싶다면 공식 문서를 살펴보자.

(https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Deque.html)

 

 

추가적으로

→ why? Stack 클래스보다 Deque인터페이스 활용을 추천하는 이유가 뭘까?

많은 말들이 있었지만 StackOverflow를 뒤지며 가장 정확해보이는 설명을 가지고 왔다.

1. Object oriented design : Stack은 클래스이고 Deque는 인터페이스 이다. 단일 클래스에서 클래스는 하나만 상속받을 수 있지만 인터페이스는 여러 인터페이스를 상속받을 수 있다. 따라서 인터페이스를 활용하는 것이 구체적인 클래스를 활용하는 것 보다 의존성을 낮추고 더 유연한 활용이 가능하다.

2. Inconsistency : Stack클래스는 Vector클래스를 상속한다. Vector클래스 doc을 보면 알 수 있듯이 element를 인덱스로 접근할 수 있다. 이것은 실질적으로 Stack이 하는 일과는 일치하지 않는다. 따라서 FIFO/LIFO잘 구조에는 Deque인터페이스가 더 적합하다.

3.Performance : Stack 클래스는 ArrayList의 "thread-safe"한 버전이다. synchronization한 자료구조를 제공하기 때문에 코테에서는 Deque인터페이스를 활용하는 것이 성능이 더 좋다.

(https://stackoverflow.com/questions/12524826/why-should-i-use-deque-over-stack)

 

 

 

개인 공부용이기 때문에 잘못된 정보가 있다면 알려주시면 감사하겠습니다!