스택
- 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
- 스택에 저장된 자료는 선형 구조를 갖는다.
- 선형 구조 : 자료 간의 고나계가 1 : 1의 관계를 갖는다
- 비선형 구조 : 자료 간의 관계가 1 : N의 관계를 갖는다. (예 : 트리)
- 후입선출구조 (LIFO, Last-In-First-Out)
- 마지막에 삽입한 자료를 가장 먼저 꺼낸다.
- ex) 스택에 1,2,3 순서로 삽입한 후 꺼내면 3,2,1 순으로 꺼내진다.
java.util.Stack
- 주요 메서드
- push() : 저장소에 자료를 삽입
- pop() : 저장소에서 자료를 삭제
- isEmpty() : 스택이 비었는지를 true or False로 리턴
- size() : 스택의 원소의 개수를 리턴
- peek() : 스택의 top에 있는 원소를 리턴
스택의 활용
1. 괄호 검사
2. fuction call
3. 계산기
4. 브라우저
큐
- 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
- 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조
- 선입선출구조 (FIFO : First In First Out)
- 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제됨
java.util.Queue
- LinkedList보다 ArrayDeque를 활용하는게 더 빠르다
- 주요 메서드
- offer() : 저장소에 자료를 삽입
- poll() : 저장소에서 자료를 삭제
- isEmpty() : 큐가 비었는지를 true or False로 리턴
- size() : 큐의 원소의 개수를 리턴
- peek() : 큐의 front에 있는 원소를 리턴
큐의 활용
1. 버퍼 (입출력 및 네트워크)
우선순위 큐
- 우선순위를 가진 항목들을 저장하는 큐
- 선입선출 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.
java.util.PriorityQueue
- Heap 자료구조
- 최대 힙 : 가장 큰 값을 기준으로 먼저 나옴
- 최소 힙 : 가장 작은 값을 기준으로 먼저 나옴
