자료구조

여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의하는 것

• 특정한 상황에 놓인 문제를 해결하는데 특화

data: 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값

• 분석하고 정리하여 활용해야 의미를 가짐
• 필요에 따라 데이터의 특징을 잘 파악(분석)하여 정리하고, 활용
  ex) 번호를 다 알지 않아도, 이름을 아는 것만으로 전화를 할 수 있는 방법은 무엇이 있을까?
  웹 브라우저에서 뒤로 / 앞으로 가는 방법은 무엇이 있을까?
  게임 매칭을 잡을 때, 수많은 사람을 통제하는 방법엔 무엇이 있을까? ...등등

Stack (스택)

데이터를 순서대로 쌓는 구조

1. LIFO: Last In First Out ( == FILO: First In Last Out)
   • 먼저 들어간 데이터는 제일 나중에 나오는 후입선출 구조
2. 데이터는 하나씩 넣고 뺄 수 있다.
   • 데이터 넣기 PUSH, 데이터 꺼내기 POP
3. 하나의 입출력 방향

사용 사례

재귀 알고리즘을 사용하는 경우 스택이 유용

• 재귀 알고리즘
  - 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
  - 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
  - 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
  - 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
  - Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
• 후위 표기법 계산
  

method

• push(E item)
  해당 item을 Stack의 top에 삽입
  Vector의 addElement(item)과 동일
• pop()
  Stack의 top에 있는 item을 삭제하고 해당 item을 반환
• size()
  Stack에 추가된 데이터의 크기를 리턴
• peek()
  Stack의 top에 있는 item을 삭제하지않고 해당 item을 반환
• empty()
  Stack이 비어있으면 true를 반환 그렇지않으면 false를 반환
• show()
  현재 Stack에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴합니다.
• clear()
  현재 Stack에 포함되어 있는 모든 데이터 삭제합니다.
• search(Object o)
  해당 Object의 위치를 반환

---

Queue (큐)

한쪽 끝에서는 삽입 작업이 이루어지고, 반대쪽 끝에서는 삭제 작업이 이루어 지는 자료구조

1. FIFO: First In First Out (== LILO: Last In Last Out)
   • 먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조
2. 데이터는 하나씩 넣고 뺄 수 있음
   • 데이터 넣기 enqueue, 데이터 꺼내기 dequeue
3. 두 개의 입출력 방향
   • 입력과 출력의 방향이 고정되어 있으며, 두 곳으로 접근 가능

데이터가 입력된 순서대로 처리할 때 주로 사용

사용 사례

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용

• 너비 우선 탐색(BFS, Breadth-First Search) 구현
  • 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
  • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
  • 노드를 접근한 순서대로 처리할 수 있다.
• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리

method

• add()
  큐에 데이터를 추가
• poll()
  가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴
• size()
  큐에 추가된 데이터의 크기를 리턴
• peek()
  큐에 가장 먼저 추가된 데이터를 리턴
  큐에서 가장 위에 있는 항목을 리턴
• show()
  큐에 들어있는 모든 데이터를 String 타입으로 변환하여 리턴
• clear()
  큐에 들어있는 모든 데이터를 삭제
• remove()
  리스트의 첫 번째 항목을 제거
• isEmpty()
  큐가 비어 있을 때에 true를 반환

ref.
https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html
https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html