2.2) 배열로 구현하는 스택과 큐의 시간 복잡도

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

배열

기본적인 배열에서 첫 부분을 제거하거나 추가하기 위해서는 요소들을 하나하나 뒤로 당겨주어야 하므로 시간복잡도가 O(n)이다. 스택과 큐를 하기에는 비효율적이므로 이러한 기본적인 배열은 거의 사용되지 않는다.

• 배열 addLast, removeLast 시간 복잡도: O(1)
• 배열 addFirst, removeFirst 시간 복잡도: O(n)

 

스택(stack)

Boivie/Wikipedia: Stack

스택은 LIFO(Last in, First out - 후입선출)의 방식으로, top으로 정한 한 곳을 통해서만 접근이 가능하다. 

책과 물건을 아래서부터 위로 쌓아올려 꺼낼 때 위에서부터 들어내어 꺼내는 양상에 빗댈 수 있다.

 

배열로 스택을 구현하면 마지막 요소에 새롭게 추가하고 다시 제거하면 된다.(addLast, removeLast) 따라서 시간복잡도는 O(1)로 상수 시간이다.

 

단일 연결 리스트로 스택을 구현하여도 리스트에서 head에 add하는 방식과 마찬가지로 top에 push하여 추가하고 pop하면 요소를 top에서 제거하면 된다. 따라서 시간복잡도는 역시 O(1) 상수 시간이다.

 

boolean	empty ()	스택이 비어 있는지 알려준다.
E	peek ()	스택 최상단의 요소를 반환하지만 스택을 수정하지는 않는다.
E	pop ()	스택 최상단의 객체를 제거하고 해당 객체를 함수의 값으로 반환한다.
E	push (E item)	스택의 최상단에 요소를 추가한다.
int	serach (Object o)	스택에서 객체가 있는  1기반 위치를 반환한다.

 

큐(queue)

Vegpuff/Wikipedia : Queue

큐는 FIFO(First in, First out - 선입선출)의 방식으로 일반 스택과 달리 리어 (rear)에서는 삽입(Enqueue) 연산이, 프론트(front)에서는 삭제(DeQueue)가 수행된다. 즉, 양쪽 끝에서 삽입과 삭제가 각각 이루어진다. 

물건을 사려고 줄을 지어 들어가다가 구입한 후 차례로 나오는 양상으로 빗댈 수 있다.

 

배열로 큐를 구현하면 삽입 시 시간복잡도 O(1), 삭제 시에는 한 칸씩 모두 앞으로 옮겨주어야 하기 때문에 O(n)이다.

 

원형 배열로 환형 큐를 구현하면 시간 복잡도 O(1)로 더 효율적이다. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결한다. 즉 배열의 양쪽의 끝이 연결되어, index 를 따라서 앞에 있는 값을 추가하고 빼다가  index 가 maxSize에 도달하면 0으로 초기화 하여 다시 처음부터 돌게 만드는 방식이다.

배열이 차 있을 때와 비어있을 때 모두 tail과 head는 같은 인덱스를 가리키며 배열에 있는 요소의 개수가 배열 크기와 같으면 모두 차 있는 것이므로, head(tail)의 인덱스를 배열 크기로 나눈 나머지를 통해 배열이 차 있는지를 파악할 수 있다. 

 

 

배열과 연결리스트의 차이점(장단점)

2-1) 연결 리스트, 노드와 크기

위에서도 언급되었는데, 배열과 연결 리스트의 장단점을 다시 정리하면 아래와 같다. 

 

 

배열 

• 처음에 선언한 배열의 크기가 고정되어 있어 적절한 크기로 만들지 않으면 조정에 불편함이 따른다. (예를 들어 처음 할당한 크기만큼 배열이 다 차게 되면 두 배로 늘려 새로운 위치로 옮겨야 한다.)
• 연결 리스트의 작업과 비교했을 때 전형적으로 더 빠른 편이며 메모리를 덜 차지한다.

 

연결 리스트

• 항상 맞는 크기로 만들어지도록 설계된다. 수용량이 정해져 있지 않으며 메모리가 부족할 때까지 계속해서 추가할 수 있다.
• 배열처럼 메모리에 연속적으로 나열되는 것이 아니라 데이터들이 연속적으로 나열되는 것이다.
• 따라서 삽입과 삭제가 용이하다. but 색인 시에는 시간이 걸린다.
• 일반적으로 배열보다 더 느리고 더 많은 메모리가 필요하다. (next 포인터를 위한 공간 등)