![]()
Queue API Queue 자료구조는 Stack과 정반대의 특성을 지닙니다. 대표적으로 FIFO, 들어온 순서대로 나가는 특성을 지니고 있죠. Queue: linked-list representation 파이썬에서는 포인터라는 개념이 없기 때문에 더욱 어색하지만 개념은 간단한 것 같습니다. 아이템을 추가할 때는 맨 앞에, 제거할 때는 맨 뒤에서 하다보니 가리키는 주소값이 두 군데여야 한다는 것입니다. Queue dequeue: linked-list implementation Queue: linked-list implementation in Java 굳이 파이썬으로 이런 코드를 짤 필요는 없는 것 같습니다.. 단순히 deque를 불러와서 추가할 줄만 알면 충분합니다. 참고로 popleft를 쓰면 배열의 ..
![]()
Stack : resizing-array implementation array의 크기를 재조정하는 것은 아주아주 비효율적인 방식입니다. 왜냐하면 크기를 재조정할 때마다 배열의 모든 아이템을 복사해야 하기 때문이죠. 이러한 경우 N개의 아이템을 삽입할 때, 총 연산 횟수는 (N^2) / 2이기 때문에 N이 충분히 클 때는 활용 불가능한 방식입니다. 따라서 배열의 크기를 매번 재조정하는 것이 아니라, 배열이 꽉 찼을 때만 이를 두 배로 늘리는 방식을 사용합니다. 이때는 N개의 아이템을 삽입할 때 N만큼의 시간이 걸립니다. Stack : amortized cost of adding to a stack Stack : resizing-array implementation 배열의 크기를 줄일 때도, 그 작업을 매번..
