Stack

Stack : resizing-array implementation array의 크기를 재조정하는 것은 아주아주 비효율적인 방식입니다. 왜냐하면 크기를 재조정할 때마다 배열의 모든 아이템을 복사해야 하기 때문이죠. 이러한 경우 N개의 아이템을 삽입할 때, 총 연산 횟수는 (N^2) / 2이기 때문에 N이 충분히 클 때는 활용 불가능한 방식입니다. 따라서 배열의 크기를 매번 재조정하는 것이 아니라, 배열이 꽉 찼을 때만 이를 두 배로 늘리는 방식을 사용합니다. 이때는 N개의 아이템을 삽입할 때 N만큼의 시간이 걸립니다. Stack : amortized cost of adding to a stack Stack : resizing-array implementation 배열의 크기를 줄일 때도, 그 작업을 매번..

Stacks and queues Stack : 가장 최근(마지막)에 추가된 아이템을 확인하는 자료구조 Queue : 가장 처음에 추가된 아이템을 확인하는 자료구조 Client, implementation, interface Stack API Stack과 관련된 아주 기본적인 method입니다. stack에 아이템을 추가하는 push, 마지막 아이템을 제거하며 반환하는 pop, stack이 비었는지 확인하는 isEmpty 등이 있습니다. 물론 Java 기준이기 때문에 Python과 약간의 차이는 있지만 LIFO 구조 자체는 동일합니다. Stack test client 아주 간단한 stack 예제 입니다. 문자열이 '-'과 동일할 땐 pop하며 출력, 그렇지 않을 땐 stack에 추가합니다. 따라서 예시는 ..