[자료구조] Stack / Queue

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) 구현
• 큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

<참고>
https://devuna.tistory.com/22