Stack
스택이란?
스택(stack)이란 쌓아 올린다는 것을 의미한다.
따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.
⇒ LIFO(Last Input First Output) : 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다.
스택의 특징
- 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있다.
- top으로 정한 곳을 통해서만 접근할 수 있다.
- top은 가장 위에 있는 자료, 최근 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
- 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.
스택의 사용
public class StackExample{
public static void main(String[] args){
Stack<String> stack = new Stack<>();
//Stack에 데이터 추가
stack.push("Data1");
//Stack에서 데이터 꺼내기
stack.pop();
//Stack의 최상단 값 출력 (제거하지 않음)
stack.peek();
//Stack에 들어있는 데이터의 개수를 리턴
stack.size();
//Stack이 비어있는지 여부를 판단(boolean)
stack.empty();
//Stack에 특정 데이터가 포함되어 있는지 체크
stack.contains("Data1");
//Stack안에 찾으려는 데이터가 있으면 위치 리턴, 없으면 -1
stack.search("Data1");
}
}- 📌 스택의 활용 예시
- 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
- 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
- 후위 표기법 계산
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
- 스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.
Queue
Queue란?
흔히 접할 수 있는 순서대로 처리하는 형태이다.
물건을 구매하기 위해 줄을 선 순서대로 살 수 있는 그러한 구조이다.
⇒FIFO(First Input First Out) : 큐는 스택과는 반대의 출력으로 먼저 들어온 데이터가 먼저 나가게 되는 방식이다.
큐의 특징
- 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
- 큐는 들어올 때 rear로 들어오지만 나올때는 front로 빠지는 특성
- 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제
- 마지막에 삽입한 요소를 삭제하기 위해서는 앞에 요소들이 전부 삭제되어야 한다.
⇒ 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫번째 원소가 되는 것이며, 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.
큐의 사용
//자바에서 큐는 LinkedList를 활용하여 생성합니다.
import java.util.LinkedList;
import java.util.Queue;
public static void main(String args[]){
//Queue선언 방식
Queue<String> queue = new LinkedList<>();
//Queue에 값추가
queue.add("Data1");
queue.offer("Data1");
//Queue에서 값 삭제
queue.poll(); //첫번째 값을 반환하고 제거
queue.remove(); //첫번째 값 제거
queue.clear(); //queue 초기화
//Queue에 rear값 참조
queue.peek();
//Queue에 담긴 데이터의 갯수 구하기
queue.size();
}- 📌 큐의 활용 예시
- 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 캐시(Cache) 구현
- 큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.
