[CS/자료구조] Array를 이용한 스택과 큐의 시간 복잡도

https://www.boostcourse.org/cs204/lecture/625951/?isDesc=false 

자바로 구현하고 배우는 자료구조

배열(array)에서 스택과 큐를 구현할 때 시간 복잡도는 어떻게 될까?

 

array를 통한 스택(Stack) 구현은 강의에서 만든 addLast, removeLast 메소드(맨뒤 추가, 맨뒤 삭제)를 이용하면 결국 둘 다 O(1)의 시간복잡도가 나와서 구현 가능하다. addFirst, removeFirst 조합으로 하면 각각 시간복잡도가 O(n)이기 때문에 절대 안된다.

-> Array로 Stack 구현 가능!

하지만 큐(Queue)의 경우 addLast, removeFirst의 조합이나 addFirst, removeLast의 조합으로 가야하기 때문에 어떤 조합으로든지 시간복잡도 O(n)이 나온다. 그래서 기본적으로 큐를 구현할 수 없다.

 

하지만 편법(?, 교수님 표현에 따르면)을 이용해 상수시간으로 바꿔줄 수 있다(!)

바로 Circular Arrays를 이용하는 거다.(물론 head, tail 포인터도 함께 이용한다.)

빈 Array 공간을 미리 확보해두고 head를 처음 칸이 아닌 중간 칸부터 가져가면 addFirst를 상수시간내로 해낼 수 있다.

하지만 이는 작업을 위해 필요한 공간보다 큰 공간을 요구하기 때문에 완벽하지는 않다. 만약 처음 지정한 칸보다 더 많은 값이 들어오면 더 큰 공간을 또 만들고 값들을 복사하고... 시간이 더 걸릴 위험도 있다.

파이썬의 push, pop은 이 Circular Array의 방법을 이용하고 있다고 한다!

 

연결리스트, 배열 각각의 장단점이 있는 것 같다.

 

배열은 빠르고 연결리스트는 느리다

하지만 배열은 크기가 고정되어있어서 Overflow시 훨씬 시간이 더 많이 걸릴 것이고

연결리스트는 크기가 고정되어있지 않은 점에서 유용하다. 하지만 이는 또 next pointer를 가져서 추가 메모리를 요구하는 문제로 이어진다.