<자료구조(Data Structure)> 스택(Stack) 정리

스택은 Last in Fisrt Out, 또는 First int Last Out



<스택을 구현하는 3가지방법>

1. 간단한 배열을 기반으로
2. 동적 배열을 기반으로
3. 연결리스트로

1번: 공간복잡도 O(n)이고 나머진 O(1)이다.

2번: 공간복잡도 O(n)이고 나머지O(1)이다.
배열의 크기를 증가시키는 것은 비용이 매우 많이든다.
예를들어, n=1에서 한개의 요소를 추가하기 위해서는 2인 배열을 만들고 이전 배열에 있던 요소들을 새로운 배열로 복사해야 한다.
n번의 push연산의 수행시간은 T(n)(복사연산의 수)=1+2+3+....n 은 O(n^2)와 비슷해진다.
**만약 배가제곱 반복을 하여 스택의 크기를 늘린다면?
n=1에서 n=32까지 늘려간다고 가정해보자.
배열의 크기가 1,2,4,8,16일 떄 배열의 크기를 두배 늘린다.
n=1일 떄, 복사를 한 번 수행하고 n=2일때 두번 ,n=4에서는 4번 수행.
즉 1+2+4+8+16=31이다. 즉 , 배가 연산은log(n)번 수행한다.

n번의 push연산 일 때는 log(n)번 수행한다. n개 요소에 대한 push연산의 전체 시간은T(n)이 된다.(다음과 같다. 1+2+4+8+16+...n/4+n/2+n)=n*(1+2+4+8+16+....1/n)=n*(2)=O(n)


T(n)은 O(n)이 되며 분할 상환시간은O(1)이 된다.
다음의 주소에서 분할 상환시간이 무엇인지 설명해놓았다.
http://yumere.tistory.com/42

3번: 이 경우는 공간복잡도O(n)그리고 DeleteStack()의 복잡도는 O(n)이다. 순차탐색을 시행해야 하므로...




**********배열 스택과 연결리스트를 이용한 것의 비교*************8
배열: 연산은 고정시간, 비용을 많이 소요하는배가연산이 종종 수행 된다.,
(빈스택에서 시작 했을 때) 모든 n에 대한 관련된 연산-n에 비례한 분할 상환 시간을 포함한다.

연결리스트-자연스럽게 크기가 증가하고 감소한다, 모든 연산은 고정시간 O(1)이 걸린다.
모든 연산은 여분의 공간과 시간이 필요하고 참조를 사용하여 처리한다.