[Java] Stack, Deque, LinkedList

학습목표

-  자바가 제공하는 Stack, Deque, LinkedList 등을 학습하세요.

 

Stack

• Vector의 상속을 받은 클래스로 LIFO(Last-In First-Out) 으로 나중에 들어온 데이터가 처음으로 빠져나가는 구조이다.
• 기본적으로 pop,push를 제공한다. 뿐만아니라 peek으로 top에 있는 데이터를 확인할 수 있다.
• empty로 스텍이 비어있는지 확인할 수 있다.
• search로 top으로부터 얼마나 멀리 있는지 확인할 수 있다.
• * 자바에서 일관적이고 권장하는 Stack 오퍼레이션 방식은 Deque인터페이스를 이용한 ArrayDeque이다.

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

 

Deque

• 선형 자료구조 형태로 양쪽에서 삽입과 삭제가 가능한 형태이다.
• "Double ended queue"
• Deque는 얼마나 데이터를 쌓을 수 있을지 limits가 정해져 있지 않다. 하지만 deque 인터페이스는 size, capacity를 제한할 수 있는 기능을 제공한다.
• 아래와 같이 Queue, Stack의 인터페이스를 받아 기능을 제공한다.

Queue 의 기능 제공(FIFO)

Stack기능 제공(FIFO)

• List 인터페이스와 다르게 특정 index를 이용하는 기능을 제공하지 않는다.
• null 삽입이 가능하지만, null을 넣는 것을 추천하지 않습니다.

 

LinkedList

• Deque과 List를 인터페이스를 받은 자료구조로 null을 허용한다.
• 찾고 싶은 index가 있다면 시작지점 or 끝지점에서 순회하여 index를 찾는 방식이다. 특정 index가 가까운 기준으로 순회를 시작한다.
• thread-safe한 코드를 짜야 한다면 아래와 같이 wrapping해야 한다.

List list = Collections.synchronizedList(new LinkedList(...));

 

• ConcurrentModificationException가 발생하여 exception 발생 유도하는 코드가 될 수 있지만 좋은 방식의 코드입니다.

출처 : java oracle 공식문서

https://docs.oracle.com/javase/7/docs/api/java/util/Deque.html

Deque (Java Platform SE 7 )