개념 정리
| 스택(Stack) | 큐(Queue) | |
|---|---|---|
| 값 추가 | push() | offer() |
| 값 제거 | pop() | poll() |
| 구조 | LIFO (후입선출) | FIFO (선입선출) |
| 사용 예시 | 재귀, 백트래킹 | BFS, 운영체제 스케줄링 |
간단하게 형태의 구분.
// Stack 예시 (LIFO, 후입선출)
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(10); // 10 추가
stack.push(20); // 20 추가
stack.push(30); // 30 추가
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
그리고 큐는
// Queue 예시 (FIFO, 선입선출)
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
}
}이렇게 생겼다. 출력 시에는 1 2 3이 출력된다.
사용예시 설명
스택
"역추적/되돌리기"
- 재귀
함수가 자기 자신을 호출할 때, 실행중인 함수를 내부적으로 Stack에 저장하게 된다.
함수가 끝나면 마지막으로 호출된 함수부터 차례적으로 복귀(LIFO)한다.
- 백트래킹
이전상태로 돌아가기
Queue
"순차적/공평한 처리"
- BFS (Breadth-First Search, 너비 우선 탐색)
- 트리에서 가장 가까운 노드부터 차례로 방문
- 현재 방문 중인 노드를 큐에 저장하고
먼저 들어간 노드부터 꺼내서 방문
- 운영체제 스케줄링 (OS Scheduling)
- 여러 프로그램이 CPU를 공평하게 나누는 상황 etc
- 프로세스를 큐에 등록하고
- 먼저 등록된 프로그램부터 실행(FIFO)
- 실행이 끝나면 다음 프로그램으로 넘어간다.
Stack의 경우는 함수 호출이 메모리에서 일어나는 것 보니 자체적으로도 움직이는 것 같지만,
Queue는 예제에서도 BufferedReader랑 사용했었고.. 설명에도 노드라는 단어가 언급되는 걸 보면 컬렉션 인터페이스 등의 친구들과 자주 쓰이는 것 같다.
실제로 내가 예시 코드를 작성하려 했을 때에도 LinkedList가 사용되었다.
List<Integer> list = new ArrayList<>();
Set<String> set = new HashSet<>();
Queue<Double> queue = new LinkedList<>();다소 늦은 감이 있지만.. 이 List/Set/Queue 친구들이 기타 프레임워크/인터페이스들과 어떻게 상호작용하는 지에 대해 따로 노트필기를 해둬야 할 것 같다.
직접 작성하고 오류 뜨는 걸 보면서 해보려고 했는데.. 이건 그냥 객체지향 언어에서 정해진 문법인 것 같다.
[Collection 인터페이스]
├─ List 인터페이스
│ ├─ ArrayList (클래스) ← Array(배열)와 유사하지만 크기 가변
│ └─ LinkedList (클래스)
│ └─ Stack (클래스)
├─ Set 인터페이스
│ └─ HashSet (클래스)
│ └─ TreeSet (클래스)
├─ Queue 인터페이스
│ ├─ LinkedList (클래스, Queue도 지원)
│ └─ PriorityQueue (클래스)
└─ Map 인터페이스 (Collection에서 분리)
├─ HashMap (클래스)
└─ TreeMap (클래스)
[자료구조별 도식]
1. Array (배열) : [0]─[1]─[2]─[3]─[4] (고정 크기, 순서 O)
2. List (리스트) : [A]→[B]→[C]→[D] (크기 가변, 순서 O)
3. Stack (스택) : [A]←[B]←[C] (LIFO, 한쪽 입출력, push/pop)
4. Queue (큐) : [A]→[B]→[C] (FIFO, 앞에서 꺼내고 뒤에서 넣음)
5. Set (집합) : {A, B, C} (중복 X, 순서 X)
6. Map (딕셔너리) : {key1:val1, key2:val2} (키-값 쌍)
7. Tree (트리) : [A]
/ \
[B] [C]
/ \
[D] [E]
8. Graph (그래프) : [A]─[B]
│ \
[C]-[D] (복잡한 노드+간선 관계)
* 클래스는 인터페이스의 "구현체"임.
* Array는 Collection의 구현체는 아니지만, List와 구조적으로 유사.
* Map 계열은 Collection에서 분리되어 있음(직계 자식이 아님).한동안 이걸 좀 쳐다봐야 할 것 같다.
트리랑 그래프는 오히려 알고리즘 기초 강의에서 여러 번 봤어서 금방 머리에 들어오는데,
컬렉션 인터페이스에 List 인터페이스가 있고
그 List 메소드를 구현하는 데에 Stack/Queue 등의 자료구조(컬렉션)타입의 클래스를 사용,
자료구조를 작성할 때에 BufferedReader등의 IO도구나
LinkedList 등 자료구조(클래스)는 모두 클래스 선언 형식으로 만들어져 있는게
말인지 방군지😁😁😁😁😁😁😁😁😁😁😁😁😁😁
암튼 힘내자...
1분 답안 정리
배열과 연결리스트를 비교해 1분 답안 만들기
배열과 연결리스트(LinkedList) 두 가지 모두 데이터를 저장하는 순차 자료구조이다. 각 메모리에 순서대로 붙는 번호(index)가 존재하며, Map 계열과는 다르게 key 없이 값만 저장하게 된다.
배열은 크기가 고정되어있고, 값이 연속된 메모리에 저장한다. 1-2-3-4...
앞서 언급한 index를 이용하여 빠르게 값에 접근하는 것 또한 가능하다. 단, 저장되는 값의 크기들은 모두 동일해야 한다.
반면 연결 리스트는 값(노드)들이 포인터로 서로 상호연결되어있는 형식이다. 배열꽈는 다르게 java 내부적으로 '노드와 연결된 다음 노드 주소'를 따라가고, 이 과정에서야 비로소 index가 붙는다. 이처럼 각 노드마다 값과 함께 포인터가 저장되는 구조이기에 메모리를 더 사용하게 되며, 찾는 데에 시간 또한 소요된다.
스택과 큐를 비교해 1분 답안 만들기
Stack과 Queue는 데이터를 저장하고 꺼내는 순서가 반대되는 자료구조이다. 순서 처리가 달라 사용 목적이 반대이기에, 상황에 맞는 자료구조를 선택해야 한다.
Stack은 LIFO(Last In, First Out) 방식으로, 마지막에 넣은 데이터가 가장 먼저 출력되는 구조이다. 주로 함수 호출, 재귀, 되돌리기(undo) 등에서 사용된다. 웹사이트의 뒤로가기와 같은 기능이 대표적인 예시이다.
반면 Queue의 경우 FIFO(First In, First Out) 방식으로, 먼저 넣은 데이터가 먼저 나오는 구조이다. 앞에 들어간 값부터 차례대로 꺼낼 수 있다. OS의 작업 스케줄러, BFS(너비우선탐색)에서 많이 쓰인다.
연결 리스트에서 중간 노드 삭제의 시간 복잡도가 O(1)이 될 수 있나요?
없다.
중간 노드를 삭제하기 위해서는 앞에 나열된 노드들을 확인해야 한다. 반드시 head -> next -> next -> ...의 순서를 가지기에, 이 순차 탐색 과정에서 시간 복잡도는 필연적으로 O(n)이 된다.
이중 연결리스트라 하더라도 양쪽 방향 끝에서부터 탐색하기에, 시간 복잡도는 O(n)으로 불변일 듯하다.
