알고리즘 - 스택, 큐

✔스택

선형 구조 : 자료간의 관계가 1대1의 관계 (ex) 배열, 리스트, 스택, 큐, ...
비선형 구조 : 자료간의 관계가 1대N의 관계 (ex) 트리

• 스택(Stack) : 후입 선출 구조(LIFO, Last in First Out) 선형 자료 구조.
  • 후입 선출 구조 : 마지막에 삽입한 자료를 가장 먼저 출력.
    • (ex) 입력 : 1, 2, 3 순 -> 출력 : 3, 2, 1 순(입력의 역순)
• 주요 연산
  1. push : 저장소에 자료를 저장.(삽입)
  2. pop : 저장소에서 자료를 꺼냄.(삭제)
  3. peek : 스택의 top에 있는 item(원소) 반환.(출력)
• 자바 Stack API : java.util.Stack
  • push() : 삽입.
  • pop() : 삭제 및 반환.
  • isEmpty() : 비었는지 확인.
  • size() : 크기.
  • peek() : top의 원소 반환.
• 스택 응용
  • Function Call : 프로그램에서 함수 호출과 복귀에 따른 수행 순서 관리
    • 가장 마지막에 호출된 함수가 가장 먼저 실행 완료 후 복귀하는 구조.(후입 선출)
    • 함수 호출 발생시 지역변수, 매개변수, 복귀 주소 등의 정보를 스택 프레임(stack fraem)에 저장하여 시스템 스택에 삽입
    • 함수 실행 종료시 top 원소 삭제하며 복귀 주소로 복귀.
  • 계산기 : 문자열로 된 계산식이 주어질 때 스택을 이용하여 이 계산식의 값을 계산할 수 있다.
    1. 중위 표기법 수식 -> 후위 표기법 변경 (스택 이용)
    2. 후위 표기법의 수식을 스택을 이용하여 계산

중위 표기법(infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 (ex) A + B
후위 표기법(postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법 (ex) AB+

✔큐

• 큐(Queue) : 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조.
  • 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조
  • 선입 선출 구조(FIFO, First In First Out)
  • 머리(Front) : 가장 먼저 들어온 데이터(가장 먼저 삭제될 데이터의 위치)
  • 꼬리(Rear) : 가장 나중에 들어온 데이터(가장 나중에 삭제될 데이터의 위치)
• 주요 연산
  1. enQueue : 저장소에 자료를 저장.(삽입)
  2. deQueue : 저장소에서 자료를 꺼냄.(삭제)
• 자바 Queue API : java.util.Queue
  • offer() : 삽입
  • poll() : 삭제
  • isEmpty() : 큐가 비었는지 확인
  • size() : 크기