모듈러 프로그래밍의 개념

인터페이스와 구현을 분리하라!
: 사용자는 구현모르고, 인터페이스만 안다
: 구현은 사용자의 요구 모른다

1. Stack 동작방식(LIFO)

• 컴퓨터 메모리 스택
• 삽입 : push, 삭제 : pop

Stack의 연결 리스트 구현

push와 pop 명령의 시간복잡도는 O(1)

오버플로우: 스택이 비어있는데 pop 명령 실행
언더플로우: 스택이 가득 차 있는데 push 명령 실행

Linked-List

• 장점 : 최악의 경우에도, 모든 명령어 constant time 에 수행 가능
• 단점 : link 관리 추가적 시간 및 메모리 요망

Stack의 resize 알고리즘

• 배열을 동적으로 수정하는 방법?
• push, pop 할 때마다 +-1 하기엔 비용(배열접근수) 비쌈
  - 모든 아이템 복붙 -> N개 삽입 시 1 ++++ N (2차) 비용
• 목표 : resizing 과도하게 안하도록 설계

• 방법
• 배열은 항상 25% ~ 100% 차 있음

Resizing-Array

• 장점 : ALL 연산 constant amortized time 에 수행 가능
• 추가적 메모리 소요 X

Stack의 응용

1. 컴파일러가 함수를 구현하는 방법

• Function calls: 지역변수, 매개변수, 반환주소값을 push
• Return: 지역변수, 매개변수, 반환주소값을 pop

2. 주어진 infix 산술식을 계산하라

Two-Stack 알고리즘

• 확장 : 연산자 종류 추가, 연산자 우선순위 고려
  

2. Queue의 동작방식(FIFO)

• 대기열과 같은 자료구조
• 삽입 : enqueue, 삭제 : dequeue