[Algorithm Part 1] 3. Stack and Queue

수 많은 applications은, 객체들의 집합(=collection of objects)를 사용한다.

뿐만 아니라 집합의 기본 연산들(e.g., 새로운 객체 추가, 기존 객체 제거)도 사용한다. 

이번 글에서는, 이러한 요구사항에 맞게 설계된 기본적인 data types(e.g., stack, queue)에 대해 살펴볼 것이다.

stack과 queue의 차이점은 객체 제거 방식이다.

stack은 가장 최근에 추가된 객체를 제거하고, queue는 가장 늦게 추가된 객체를 제거한다.

Modular programming

모듈화 프로그램(modular programming)의 개념은 인터페이스(interface)와 구현(implementation)을 완전히 분리시키는 것이다.

• implementation: actual code implementing operations.
• interface: description of data type, basic operations.

클라이언트는 interface를 통해 간편히 basic operations을 사용하면 된다. 즉, implementation의 세부적인 요소를 알 필요가 없다. 이는 많은" 클라이언트가 쉽게 기능을 사용할 수 있다는 것" 즉, "접근성이 좋다는 것"을 의미한다.

이러한 분리는 모듈의 재사용을 가능케한다.

---

1. Stack

Stack는 객체의 집합을 가지고 있는 동시에, 추가/제거 연산을 지원하는 ADT다.

이때, 제거 연산은 가장 최근에 추가된 객체를 집합에서 제거함과 동시에 반환(return)한다.

1.1. Implementation 1: linked-list

data structure: linked-list를 사용한다.

 

1. push(): 솨슬 맨 앞 부분에 노드(=object, pointer)를 추가한다

2. pop(): 솨슬 맨 앞 노드를 제거하고 반환한다.

1.2. Implementation 2: array

data structure: 배열을 사용한다.

 

1. push(): 배열 N번째 부분에 객체를 추가한다.

2. pop(): 배열 N-1번째 부분의 객체를 제거한다.

Consideration

1. Overflow & Underflow: 대부분 클라이언트는 원하는 stack 크기를 모른다.
   때문에, 동적인 stack을 제공해줘야 한다. 
2. Null items: null 객체가 stack에 포함되는 것을 허용해줘야 한다.
3. Loitering: 제거된 객체를 더 이상 참조하지 않는다.

Performance

	pop()	push()
linked-list	1	1
array	1	1

space-complexity는 linked-list가 더 크다.

---

Resizing Array

이번에는 array stack의 overflow/underflow 문제를 해결할 것이다.

1. increase/decrase one

push()/pop()할 때마다, 배열 크기를 하나 증가/감소시킨다.

연산마다 배열 크기 조정을 시키므로, 연산 비용 N이다.

2. increase double / decrease one half

overflow 즉, 배열이 full인 경우, 배열 크기를 두 배 키운다.

underflow 즉, 배열이 1/4만 찼을 경우, 배열 크기를 반으로 줄인다.

Performance

N번의 push()연산 비용은 $N + (2 + 4 + \dots + N)$ $\sim 3N$이다.

하지만, 분할 상환 분석(=Amortized Analysis)을 사용하면, $\sim 1$ 즉, constant하다.

즉, "배열 크기 조정 이전의 push() 연산 당시, 비용을 미리 지불했다"는 뜻이다.

(Amortized analysis: average running time per operation over a worst-case sequence of operations)

	best	worst	amortized
construct	1	1	1
push	1	N	1
pop	1	N	1
size	1	1	1

Memory use : $\sim 8 N$ (when full) to $\sim 32 N$ (when one-quarter full)

Tradeoffs: linked-list VS array

Situation:Perform N pop and M push in random order.

	Linked-list	Array
worst case	$\sim 1$	$\sim N$
total cost	big	sma

---

2. Queue

Queue는 (stack와 마찬가지로) 객체의 집합을 가지고 있는 동시에, 추가/제거 연산을 지원하는 ADT다.

이때, stack와 다르게, 제거 연산은 가장 늦게 추가된 객체를 집합에서 제거함과 동시에 반환(return)한다.

2.1. Implementation1: linked-list

data structure: linked-list를 사용한다.

 

1. push(): 솨슬 맨 뒷 부분에 노드(=object, pointer)를 추가한다

2. pop(): 솨슬 맨 앞 노드를 제거하고 반환한다.

2.2. Implementation 2: array

data structure: 배열을 사용한다.

 

1. push(): 배열 tail번째 부분에 객체를 추가한다.

2. pop(): 배열 head번째 부분의 객체를 제거한다.

Performance

Stack와 동일하다.