오늘은 자료구조에 대해 강의를 듣고 구현해 보는 시간을 가졌는데, 깊이있게 공부해 본 경험은 처음이라 어려웠다.
[01. Stack]
- stack 자료구조는 후입선출 : 나중에 들어간게 처음으로 나온다(Last in First Out, LIFO) 구조입니다.
저는 세로구조라고 생각해요.. 맨 나중에 들어간 것 부터 꺼낸다 = 맨 위에서부터 꺼낸다..
일단 선언하고 데이터를 집어 넣는 것 부터 해야겠지요..
- 기본 연산
push: 스택의 맨 위에 요소를 추가.
pop: 스택의 맨 위 요소를 제거하고 그 값을 반환.
peek: 스택의 맨 위 요소를 조회.
import java.util.*;
public class StackExample {
public static void main(String[] args) {
// Stack 선언
Stack<Integer> stack = new Stack<>();
// 요소 추가
stack.push(10); // 10 추가
stack.push(20); // 20 추가
stack.push(30); // 30 추가
int peek = stack.peek();;
// 스택의 상태 출력
System.out.println("스텍은 ? " + stack);
//출력 : 스택은? [10, 20, 30]
System.out.println("스텍 맨위? " + peek);
//출력 : 스텍 맨위? 30
// 요소 추가 후 스택의 크기 출력
System.out.println(stack.size());
//출력 : 3
}
}
저는 위에 그림처럼 쌓는다라고 생각했네요. 그래서 맨 위에 쌓인 데이터를 조회할 때는 peek()를 사용해 조회해줍니다.
꺼낼때는 pop()메서드를 사용합니다.
pop 은 위에서 설명한 것 처럼 꺼내고 그 요소를 지워버립니다... 코드와 그림을 보죠..
package src.com.company.week2.day1;
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
// Stack 선언
Stack<Integer> stack = new Stack<>();
// 요소 추가
stack.push(10); // 10 추가
stack.push(20); // 20 추가
stack.push(30); // 30 추가
int poppedElement = stack.pop(); // 스택에서 요소 꺼내고 반환
// 꺼낸 요소 출력
System.out.println("꺼낸 요소는?: " + poppedElement);
// 출력 : 꺼낸 요소는 ? 30
// 꺼낸 요소를 제외한 스택의 상태 출력
System.out.println("꺼내고 난 뒤의 상태: " + stack);
// 출력 : 꺼내고 난 뒤의 상태: [10, 20]
}
}
- 사용하는 이유
1. 역추적(back tracking) : 데이터 임시저장소와 같은 역할 peek() 해서 조회해 올 수도, 원하는 값과 다르면 pop 해서
재귀적인 알고리즘, 깊이우선 탐색에서 재귀 호출할 때 함수 호출 상태를 저장할 수 있음 => 이로 인해 알고리즘의 이전 상태로 되돌아 갈 수 있음.
2. 괄호 문제 : 오늘 과제로 나온 것
괄호의 쌍이 올바르게 열고 닫혔는지, 여는 괄호가 오면 스택에 push 하고 닫는 괄호가 나오면 pop 한다.
[02. Queue]
- Queue 자료구조는 선입선출(First In First Out) 구조입니다.
저는 헷갈려서 스택만 외우는데, 큐는 짤주머니를 생각하고는 합니다.. 먼저 들어간 생크림이 먼저 나오는...?
- 기본연산
offer : 큐의 끝에 요소를 추가.
poll : 큐의 첫번째 요소를 제거 후 값 반환.
peek : stack 과 같이 맨 위의 요소를 조회
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
// Queue 선언
Queue<String> queue = new LinkedList<>();
// 요소 추가
queue.offer("짜장면"); // 요소 추가
queue.offer("치킨"); // 요소 추가
queue.offer("떡볶이"); // 요소 추가
String best = queue.peek();
// 작업 대기열 출력
System.out.println("내가 지금 먹고싶은건 " + queue);
// 출력 : 내가 지금 먹고싶은건 [짜장면, 치킨, 떡볶이]
System.out.println("가장 먹고싶은건 ? " + best);
// 출력 : 가장 먹고싶은건 ? 짜장면
}
}
이제 꺼내는 방법도 알아야.. 겠죠?
1. poll() 메서드 사용하여 하나씩 꺼내 봅시다.
package src.com.company.week2.day1;
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
// Queue 선언
Queue<String> queue = new LinkedList<>();
// 요소 추가
queue.offer("짜장면"); // 작업 추가
queue.offer("치킨"); // 작업 추가
queue.offer("떡볶이"); // 작업 추가
// 작업 대기열 출력
System.out.println("내가 지금 먹고싶은건 " + queue);
// 출력 : 내가 지금 먹고싶은건 [짜장면, 치킨, 떡볶이]
// peek은 조화만 한다
String best = queue.peek();
String first = queue.poll();
String second = queue.poll();
String third = queue.poll();
System.out.println("가장 먹고싶은건 ? " + best);
// 출력 : 가장 먹고싶은건 ? 짜장면
System.out.println("처음으로 나오는건 ? " + first);
// 출력 : 처음으로 나오는건 ? 짜장면
System.out.println("두번째로 나오는건 ? " + second);
// 출력 : 처음으로 나오는건 ? 치킨
System.out.println("세번째로 나오는건 ? " + third);
// 출력 : 처음으로 나오는건 ? 떡볶이
/** 요소 다 빼고 나서는 ? */
System.out.println("내가 지금 먹고싶은건 " + queue);
// 출력 : 내가 지금 먹고싶은건 []
}
}
2. for 문을 돌려서 요소를 다 꺼내봅시다.
package src.com.company.week2.day1;
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
// Queue 선언
Queue<String> queue = new LinkedList<>();
// 요소 추가
queue.offer("짜장면"); // 작업 추가
queue.offer("치킨"); // 작업 추가
queue.offer("떡볶이"); // 작업 추가
// 작업 대기열 출력
System.out.println("내가 지금 먹고싶은건 " + queue);
// 출력 : 내가 지금 먹고싶은건 [짜장면, 치킨, 떡볶이]
// 작업 처리 (처음에 추가된 작업부터 처리됨)
while (!queue.isEmpty()) {
String task = queue.poll(); // 작업 꺼내기
System.out.println("지금 먹고있는 것은?: " + task);
}
/**
* 출력
* 지금 먹고있는 것은?: 짜장면
* 지금 먹고있는 것은?: 치킨
* 지금 먹고있는 것은?: 떡볶이
* */
/** 요소 다 빼고 나서는 ? */
System.out.println("내가 지금 먹고싶은건 " + queue);
// 출력 : 내가 지금 먹고싶은건 []
}
}
예시를 음식으로 이야기 한건.. 시간이 시간이라.. 배고파서... 입니다...
- 사용하는 이유
1. 작업 대기열 : 여러 작업을 "순서대로" 구현해야 할 때
2. 캐시(Cache) : 새로운 뎅터가 추가되면 Queue의 맨 뒤에 추가되고, 오래된 데이터는 제거
+) 우선순위큐 ?
[03. Deque]
- Deque(Double Ended Queue) 은 양방향에서 데이터를 추가하거나 제거할 수 있다.
- Queue 와 Stack의 기능을 모두 가지고 있다.
⭐️ Deque의 구현체로는 1) ArrayDeque, 2) LinkedList 가 있다.
| ArrayDeque | LinkedList | |
| 접근 시간 | - 배열 -> 인덱스 빠른 접근(O(1)) | - 배열 순회해서 찾음(O(n)) |
| 메모리 사용 | - 연속적, 캐시효율성, 메모리 오버헤드 없음 | - 앞, 뒤 노드(참조) 가 필요해 메모리 사용량 ArrayDeque 보다 많음 |
| 언제 쓸까 ? | 요소에 대한 빠른 접근 필요할 때(조회) | 삽입, 삭제가 많이 일어날 때(값 변동) 순서가 있는 접근이 필요할 때 |
| 내부 구현 | - 동적으로 크기가 조절되는 배열 사용 - 요소 추가, 제거 가능 - 인덱스 사용해 요소에 접근 가능 |
- 이중 연결 리스트로 구현되어 있음 - 요소 추가, 제거 시 노드도 조회 - 인덱스 사용 가능하나, 데이터(요소) 조회 시, 이전노드, 다음 노드 참조 포함 |
- 기본 연산
| 값 추가 | 값 제거 | |
| 예외 있음 | - addFirst, addLast, add - IllegalStateException, 용량 초과 예외 |
- removeFirst, removeLast, remove - NoSuchElementException |
| 예외 없음 | - offerFirst, offerLast, offer - 실패 시 false 반환 |
- pollFirst, pollLast, poll - 실패 시 null 반환 |
코드와 출력문으로 봅시다..
package src.com.company.week2.day1;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
public class DequeExample {
public static void main(String[] args) {
// Deque 선언 (ArrayDeque 사용)
Deque<Integer> deque1 = new ArrayDeque<>();
// Deque에 요소 추가 (양쪽 끝에 추가)
deque1.offerFirst(1); // 맨 앞에 추가
deque1.offer(2);
deque1.offer(3);
deque1.offerLast(4); // 맨 뒤에 추가
// Deque 출력
System.out.println("데큐 1번: " + deque1);
// 출력 : 데큐 1번: [1, 2, 3, 4]
// Deque1에서 요소 제거 (양쪽 끝에서 제거)
int pollFirst = deque1.pollFirst(); // 맨 앞에서 제거
int pollLast = deque1.pollLast(); // 맨 뒤에서 제거
// 제거된 요소 출력
System.out.println("첫번째로 제거된것 ? " + pollFirst);
// 출력 : 첫번째로 제거된것 ? 1
System.out.println("마지막 제거 요소 ? " + pollLast);
// 출력 : 마지막 제거 요소 ? 4
// 남아있는 deque ?
System.out.println("맨 앞 맨 뒤 제거 후? " + deque1);
// 출력 : 맨 앞 맨 뒤 제거 후? [2, 3]
System.out.println("============================================");
Deque<String> deque2 = new LinkedList<>();
deque2.addFirst("I am first");
deque2.add("first 다음으로 넣음");
deque2.addLast("I am Last");
// Deque 출력
System.out.println("데큐 2번: " + deque2);
// 출력 : 데큐 2번: [I am first, first 다음으로 넣음, I am Last]
// Deque2에서 요소 제거 (양쪽 끝에서 제거)
String removeFirst = deque2.removeFirst(); // 맨 앞에서 제거
String removeLast = deque2.removeLast(); // 맨 뒤에서 제거
// 제거된 요소 출력
System.out.println("첫번째로 제거된것 ? " + removeFirst);
// 출력 :첫번째로 제거된것 ? I am first
System.out.println("마지막 제거 요소 ? " + removeLast);
// 출력 : 마지막 제거 요소 ? I am Last
// 남아있는 deque ?
System.out.println("맨 앞 맨 뒤 제거 후? " + deque2);
// 출력 : 맨 앞 맨 뒤 제거 후? [first 다음으로 넣음]
}
}
끝!
'프로그래밍 > 자바' 카테고리의 다른 글
| [JAVA] 자바는 call by value다.. (0) | 2024.05.24 |
|---|---|
| [JAVA] Scanner vs BufferedReader(),(BufferedWriter) 코딩테스트 무엇을 쓰는게 좋을까 (2)? (0) | 2024.03.27 |
| [JAVA] Scanner vs BufferedReader(),(BufferedWriter) 코딩테스트 무엇을 쓰는게 좋을까 (1)? (1) | 2024.03.27 |