💡 스택하고 큐는 배열 위에 어떤 규칙을 설정한 모습이다.
스택이 따라야하는 규칙을 설명하기 위해 즉 '스택'은 배열이 수직으로 쌓여있고 이 배열에선 요소를 추가하거나 삭제할 때 맨 위에서부터 차레로 할 수 있다
'큐'는 버스를 기다리는 것을 생각하면 됨 '큐'는 배열인데 이 배열에선 가장 먼저 '큐'에 입장한 요소가 가장 먼저 '큐'에서 나가는 요소가 된다
** 이것들은 '추상적'자료구조이다
STACK
데이터를 차곡차곡 쌓아 올린 형태의 자료구조
✅ 데이터가 순서대로 쌓이면 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조
✅접시를 쌓아놓는 스택이라고 생각하기 -> 가장 위의 접시부터 꺼내는 것처럼
(LIFO)
▶️ TOP : 스택의 가장 윗 부분
▶️ BOTTOM : 스택의 가장 아랫부분(바닥)
▶️ PUSH(ITEM) : 데이터를 넣는 작업
▶️ POP() : 데이터를 꺼내는 작업
▶️ PEEK() : 스택의 가장 위에 있는 항목 조회
▶️ SIZE() : list에 현재 저장되어 있는 요소의 개수를 반환한다 -> 이 메서드는 숫자를 "누출"하지 않는다
- 숫자가 누출된다는 것은 만약에 메서드가 의도치 않게 내부 데이터를 노출하거나 수정하는 것을 의미한다면 size() 메서드에서 그런 일이 발생하지 않는다
-> 단순히 현재 스택에 몇 개의 요소가 있는지를 반환한다
➡️ 함수 호출의 실행 컨텍스트를 관리하거나 DFS를 비롯한 Traceback 알고리즘 혹은 재귀 알고리즘등에서 호출을 추적할 때 사용
// 패키지 선언: 이 클래스가 "stack"이라는 패키지에 속해 있음을 의미합니다.
// 패키지 선언: 이 클래스가 "stack"이라는 패키지에 속해 있음을 의미합니다.
package stack;
import java.util.LinkedList; // LinkedList 클래스를 사용하기 위해 가져옵니다.
public class Stack<T> { // Stack이라는 제네릭 클래스를 정의합니다. <T>는 스택에 저장할 데이터 타입을 지정하기 위해 사용됩니다.
private final LinkedList<T> list = new LinkedList<>(); // LinkedList를 사용하여 스택의 내부 데이터를 저장할 리스트를 만듭니다. 'final'은 리스트 객체를 다시 할당할 수 없게 합니다.
// 스택이 비어있는지 확인하는 메서드입니다.
public boolean isEmpty() {
return list.isEmpty(); // list가 비어있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
}
// 스택에 데이터를 추가하는 메서드입니다.
public void push(T item) {
list.addLast(item); // list의 마지막에 아이템을 추가합니다. 이 아이템은 스택의 가장 위에 쌓이게 됩니다.
}
// 스택에서 데이터를 제거하고 반환하는 메서드입니다.
public T pop() {
if (isEmpty()) { // 스택이 비어있다면 예외를 발생시킵니다.
throw new IllegalStateException("스택이 비어 있습니다"); // 예외 메시지를 출력하며 프로그램이 이 상태에서 계속 진행되지 않도록 합니다.
}
return list.removeLast(); // 스택의 가장 마지막에 있는 데이터를 제거하고, 그 값을 반환합니다.
}
// 스택의 가장 위에 있는 데이터를 확인하는 메서드입니다. (제거하지 않음)
public T peek() {
if (isEmpty()) { // 스택이 비어있다면 예외를 발생시킵니다.
throw new IllegalStateException("스택이 비어 있습니다"); // 예외 메시지를 출력합니다.
}
return list.getLast(); // 스택의 가장 마지막에 있는 데이터를 반환하지만, 제거하지는 않습니다.
}
// 스택에 있는 데이터의 개수를 반환하는 메서드입니다.
public int size() {
return list.size(); // list에 저장된 데이터의 개수를 반환합니다.
}
// main 메서드는 프로그램이 실행될 때 처음 호출되는 메서드입니다.
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>(); // Integer 타입의 데이터를 저장할 Stack 객체를 생성합니다.
stack.push(10); // 스택에 10을 추가합니다.
stack.push(20); // 스택에 20을 추가합니다.
System.out.println("가장 위의 아이템: " + stack.peek()); // 스택의 가장 위에 있는 데이터를 출력합니다. (여기서는 20)
System.out.println("제거된 아이템: " + stack.pop()); // 스택에서 가장 위에 있는 데이터를 제거하고, 그 값을 출력합니다. (여기서는 20을 제거)
System.out.println("스택의 크기: " + stack.size()); // 스택에 남아있는 데이터의 개수를 출력합니다. (여기서는 1)
}
}
가장 위의 아이템: 20
제거된 아이템: 20
스택의 크기: 1 private final LinkedList<T> list = new LinkedList<>(); //'final'은 리스트 객체를 다시 할당할 수 없게 합니다.- final 키워드를 사용한 이유 : 코드에서 특정 객체가 재할당되지 않도록 하기 위함.
final의 의미 :
- 변수가 사용될 때 이 변수에 값이 한 번 할당되면 더 이상 다른 값으로 재할당될 수 없습니다. 즉 이 변수는 상수처럼 동작한다
- 클래스에 사용될 때 이 클래스는 더 이상 상속될 수 없습니다
- 메서드에 사용될 때 이 메서드는 더 이상 오버라이드(재정의)될 수 없다
** final 키워드를 list에 사용한 이유
list 변수에 한 번 객체가 할당되면 이 변수는 다른 LinkedList 객체나 다른 타입의 객체로 변경될 수 없음을 의미한다
이 경우 list 변수는 한 번 초기화된 후에 다른 값으로 변경되지 않도록 고정된다
-- final의 실제 필요성
사실, final 키워드를 사용하지 않아도 이 코드가 문제없이 동작합니다. final 키워드는 코드를 더 안전하게 만들고, 객체의 참조가 재할당되지 않도록 보장하기 위해 사용됩니다. 예를 들어, 실수로 list 변수에 다른 LinkedList 객체를 할당하는 것을 방지할 수 있습니다
- final을 제거해도 기능적으로 문제없다 언제든지 상황에 따라 사용할지말지 결정하면됨
LikedList
: 자바에서 제공하는 자료구조, 데이터를 노드의 형태로 저장하며, 각 노드는 다음 노드에 대한 참조(링크)를 가지고 있는 방식의 리스트이다
✔️ 자료구조의 형태
- 단일 연결 리스트 : 각 노드는 다음 노드만 가리킨다
- 이중 연결 리스트 : 각 노드는 이전 노드와 다음 노드를 모두 가리킨다. 자바의 LinkedList는 이중 연결 리스트를 구현한 것이다
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
// 요소 추가
list.add("첫 번째");
list.add("두 번째");
list.add("세 번째");
// 첫 번째 요소 제거
list.removeFirst();
// 리스트 출력
for(String item : list) {
System.out.println(item);
}
}
}Queue
먼저 들어간 데이터를 먼저 꺼내는 자료구조 (FIFO)
✅ 일상생활에서 웨이팅을 기다리는 것과 비슷하다
▶️ FRONT : 데이터를 꺼내는 쪽(맨앞)
▶️ REAR : 데이터를 넣는 쪽 (맨 뒤)
▶️ enqueue(item) : 데이터를 넣는 작업
▶️ dequeue() : 데이터를 꺼내는 작업
▶️ PEEK() : 큐의 가장 앞에 있는 항목 조회
import java.util.LinkedList;
public class Queue<T> { // 제네릭을 사용하여 큐에 다양한 타입의 데이터를 저장할 수 있습니다.
private LinkedList<T> list = new LinkedList<>(); // 큐의 내부 데이터 저장을 위한 LinkedList 사용
// 큐가 비어 있는지 확인하는 메서드
public boolean isEmpty() {
return list.isEmpty();
}
// 큐의 끝에 데이터를 추가하는 메서드
public void enqueue(T item) {
list.addLast(item); // LinkedList의 끝에 데이터를 추가합니다.
}
// 큐의 앞에서 데이터를 제거하고 반환하는 메서드
public T dequeue() {
if (isEmpty()) { // 큐가 비어 있다면 예외를 발생시킵니다.
throw new IllegalStateException("Queue is empty"); // 예외 메시지 출력
}
return list.removeFirst(); // 큐의 앞에서 데이터를 제거하고 반환합니다.
}
// 큐의 앞에 있는 데이터를 제거하지 않고 반환하는 메서드
public T peek() {
if (isEmpty()) { // 큐가 비어 있다면 예외를 발생시킵니다.
throw new IllegalStateException("Queue is empty"); // 예외 메시지 출력
}
return list.getFirst(); // 큐의 앞에 있는 데이터를 반환하지만, 제거하지는 않습니다.
}
// 큐에 있는 데이터의 개수를 반환하는 메서드
public int size() {
return list.size(); // list에 저장된 데이터의 개수를 반환합니다.
}
// 테스트용 main 메서드
public static void main(String[] args) {
Queue<Integer> queue = new Queue<>(); // Integer 타입의 데이터를 저장할 Queue 객체 생성
queue.enqueue(10); // 큐에 10 추가
queue.enqueue(20); // 큐에 20 추가
System.out.println("Front item: " + queue.peek()); // 큐의 앞에 있는 아이템 출력 (여기서는 10)
System.out.println("Dequeued item: " + queue.dequeue()); // 큐에서 아이템 제거 후 출력 (여기서는 10)
System.out.println("Size of queue: " + queue.size()); // 큐에 남아있는 아이템 개수 출력 (여기서는 1)
}
}
}✅ 큐는 일반적으로 다음과 같은 상황에서 사용된다
- 작업이나 요청을 처리할 때, 요청이 들어온 순서대로 처리해야 하는 경우
- BFS(너비 우선 탐색) 같은 알고리즘에서 탐색의 순서를 유지할 때
💡💡 언제 '큐'를 쓰고 '스택'을 쓰는가
웹 브라우저에서 '뒤로가기'를 누르면 '스택' 자료구조를 쓰는 것이다
왜냐하면 '뒤로가기'를 누른다는 것은 웹 페이지 히스토리 스택의 맨 위에서 한 페이지를 가져가는 것이다.
혹은 뭔가를 쓰다가 '되돌리기'를 하면 이거 역시 스택이다
'큐'는 이메일 알림이나 푸쉬 알림 기능 쇼핑몰에서 주문을 처리하는 방식(선착순) 콜센터의 백엔드가 될 수 있다 전화 온 순서대로 상담을 처리하는 것처럼
