[자료구조] Stack과 Queue

1. Stack

• 후입선출(LIFO, Last In First Out) 방식의 자료구조
• 특징
  • 스택 내부의 데이터는, top을 통해서만 접근 가능
    • top은 가장 최근(마지막)에 들어온 자료나 데이터를 의미
  • 스택에 데이터를 삽입할 때는, top 위에쌓이게 되며('push' 연산)
  • 스택에서 데이터를 삭제할 때는, top에 위치한 데이터를 삭제하게 된다. (pop 연산)
  • 즉, 스택은 시간 순서에 따라 데이터가 쌓이게 되므로 가장 마지막에 삽입된 데이터가 가정 먼저 삭제된다는 특징을 가지게 된다.
• 활용 예시
  • 웹 브라우저 방문기록(뒤로 가기)
  • 실행 취소(undo)
  • 역순 문자열 만들기
  • 후위 표기법 계산
    • A+B*C 가 아닌 ABC*+ 로 표기하는 것
  • 수실의 괄호 검사
    • 연산자 우선순위 표현을 위한 괄호 검사

2. Queue

• 선입선출(FIFO, First In First Out) 방식의 자료구조
• 특징
  • 큐는 삽입, 삭제가 다른 방향에서 이루어진다.
  • 삭제 연산만 수행되는 곳은 front, 삽입 연삼나 수행되는 곳을 rear라고 한다.
    • 프론트에서 이루어지는 삭제 연산을 dnQueue(디큐) 라고 하며
    • 리어에서 이루어지는 삽입 연산을 enQueue(인큐) 라고 한다.
  • 즉 가장 먼저 삽입된 데이터가 가장 먼저 삭제 된다는 특징이 있다.
• 활용 예시
  
  •  
  • 데이터가 입력된 순서에 따라 처리되어야 하는 경우에 주로 사용
  • 줄서서 기다리는 모든 행동
    • 은행 업무
    • 콜센터 고객 대기시간
    • 놀이동산
  • 프로세스 관리
  • 너비 우선 탑색(BFS, Breadth-First Search) 구현
  • 캐시(Cache) 구현