java 자료구조(스택, 큐, 데큐)

ArrayList VS LinkedList

• ArrayList:
  • 내부적으로 동적 배열을 사용하여 데이터를 저장한다.
  • 메모리 상에 연속된 공간에 데이터를 저장하므로 인덱스를 사용한 접근 속도가 빠르다.
• LinkedList:
  • 내부적으로 이중 연결 리스트로 데이터를 저장한다.
  • 각 요소는 노드로 구성되어 있으며, 각 노드는 데이터와 다음 및 이전 노드를 가리키는 포인터를 포함한다.
  • 메모리 상에 비연속적으로 데이터를 저장할 수 있다.
  • LinkedList는 Deque, Queue, List 인터페이스 모두 구현

LinkedList 대신 ArrayList를 사용할 수도 있지만, 삽입/삭제가 많은 경우 LinkedList가 유리하다.

 

선형자료구조

스택(Stack)

 

큐(Queue)

 

덱(Deque)

 

우선순위큐(PriorityQueue)

 

원형 큐(Circular Queue)

 

이중연결리스트(양방향 연결 리스트)

 

비선형 자료구조

트리

 

그래프

 

힙 

 

트라이

 

...

---

 

스택이란? 

https://inpa.tistory.com/entry/JCF-%F0%9F%A7%B1-Stack-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%A0%95%EB%A6%AC

🧱 자바 Stack 구조 & 사용법 정리

 

 

Stack 클래스보다 Deque를 쓸 것을 권장한다. 

 

백준 예제 문제

- https://www.acmicpc.net/problem/1935 (후위표기식2)

- https://www.acmicpc.net/problem/1874 (스택수열)

 

 

큐?

https://kwin0825.tistory.com/157

[JAVA / 자바] Queue(큐) 클래스 사용법 및 함수(Method) 정리

백준 예제 문제

- https://www.acmicpc.net/problem/18258 (큐 기본)

- https://www.acmicpc.net/problem/11866 (요세푸스 문제)

 

 

 

 

덱?

https://hbase.tistory.com/128

[Java] Deque (덱/데크) 사용법 및 예제

 

백준 예제 문제

- https://www.acmicpc.net/problem/10866 (덱 기본)

- https://www.acmicpc.net/problem/1021 (회전하는 큐)

 

우선순위 큐

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

[Java] Priority Queue(우선 순위 큐)