[CS] 자료구조 : Java와 Stack, Queue

✏️Stack

마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO 구조

🔸Java - Stack 클래스 메서드

java.util 패키지에 Stack 클래스로 정의되어 있다. Stack 클래스는 Vector 클래스를 상속받아 구현되었으며, 기본적인 메서드들을 제공한다.

1. push : item을 스택의 맨 위에 추가한다.
2. pop : 스택의 맨 위에 있는 객체를 제거하고, 그 객체를 반환한다.
3. peek :  스택의 맨 위에 있는 객체를 반환하지만, 객체 자체는 스택에서 제거하지 않는다.
4. empty : 스택이 비어있는지 여부를 확인한다.
5. search : 인자로 전달된 객체가 스택의 몇 번째 위치에 있는지를 반환한다.

🔸Java에서의 Stack 활용

1. 함수 호출 스택
     자바에서 메서드 호출 시, 호출된 메서드의 정보는 스택에 push 되며, 메서드가 종료되면 해당 메서드 정보는 스택에서 pop 되어 제거된다. 이러한 과정을 통해 메서드의 실행 순서를 관리하고, 메서드가 끝날 때마다 필요한 리소스를 해제한다.
2. 후위 표기식 계산
     수식을 후위 표기식으로 변경할 때 스택을 사용한다. 연산자는 스택에 push 되고, 피연산자가 나타나면 스택에서 pop 하여 계산을 진행한다.
     후위 표기식이란 연산자를 피연산자 뒤에 표기하는 방식이다. 예를 들어 2 + 3이 2 3 + 로 표현되는 것이다. 2와 3을 스택에 push 하고 + 연산자를 만나면 두 개의 피연산자를 pop 하여 더하고 그 결과를 스택에 push 한다.
3. 괄호 검사
     프로그래밍에서 괄호의 짝이 맞는지 검사할 때 스택을 사용한다. 여는 괄호는 스택에 push 하고, 닫는 괄호가 나타나면 스택에서 pop 하여  짝을 검사한다.
4. DFS(깊이 우선 탐색)
     그래프나 트리를 탐색할 때 스택을 사용하는 깊이 우선 탐색 알고리즘이 있다. 방문한 노드를 스택에 push 하고, 더 이상 방문할 노드가 없을 때 스택에서 pop 하여 이전 노드로 돌아간다.
5. 페이지 이동 기록
     웹 브라우저의 뒤로 가기 기능을 구현할 때 스택을 사용한다. 방문한 페이지의 URL을 스택에 push 하고, 뒤로 가기를 누르면 스택에서 pop 하여 이전 페이지로 돌아간다.

---

✏️Queue

처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO의 구조

🔸Java - Queue 클래스 메서드

java.util 패키지에 Queue 인터페이스로 정의되어 있고, 주요 메서드들은 다음과 같다.

1. add : 큐의 맨 뒤에 요소를 추가한다. 성공적으로 추가되면 true를, 공간이 부족하여 추가할 수 없으면 IllegalStateException을 발생시킨다.
2. offer : 큐의 맨 뒤에 요소를 추가한다. 성공적으로 추가되면 true를, 공간이 부족하여 추가할 수 없으면 false를 반환.
3. remove : 큐의 맨 앞에 있는 요소를 제거하고 반환한다. 큐가 비어있는 경우 NoSuchElementException을 발생시킨다.
4. poll : 큐의 맨 앞에 있는 요소를 제거하고 반환한다. 큐가 비어있는 겨우 null을 반환.
5. element() : 큐의 맨 앞에 있는 요소를 반환하지만 제거하지는 않는다. 큐가 비어있는 경우 NoSuchElementException을 발생시킨다.
6. peek() : 큐의 맨 앞에 있는 요소를 반환하지만 제거하지는 않는다. 큐가 비어있는 경우 null을 반환한다.

🔸Java에서의 Queue 활용

1. 작업 스케줄링
     큐는 작업을 순서대로 처리해야 하는 작업 스케줄링에 사용된다.
2. BFS(너비 우선 탐색)
     그래프나 트리를 탐색할 때 큐를 사용하는 너비 우선 탐색 알고리즘이 있다. 루트 노드부터 시작하여 인접한 노드를 모두 방문한 후, 그다음 레벨의 노드들을 방문하는 방식으로 진행된다. 이때 방문해야 할 노드들을 큐에 저장하며, 큐에서 노드를 하나씩 꺼내가며 탐색을 진행한다.
3. 캐싱
     큐를 사용하여 최근에 사용된 아이템을 추적하는 캐싱 알고리즘을 구현할 수 있다. 이는 특히 메모리 관리에 유용하다. 최근에 사용된 아이템이나 페이지를 큐에 저장하고, 큐가 가득 차면 가장 오래전에 사용된 아이템을 제거한다.
4. 데이터 버퍼링
     데이터를 순차적으로 처리해야 하는 경우, 큐를 데이터 버퍼로 사용할 수 있다. 예를 들어, 네트워크 통신에서 데이터 패킷을 순서대로 처리하기 위해 큐를 사용하며, 패킷이 도착하면 큐에 추가하고 순서대로 처리한다.