4. Bag, Stack, Queue

bag, stack, queue는 모두 collection of object로,  insert, remove, iterate, isEmpty의 연산을 가진다.

 

Bag는 내부 item의 순서가 없고, 삽입과 랜덤한 순서로 iterate만 가능하다.

Stack은 LIFO(Last In First out), Queue는 FIFO(First In First Out)의 구조를 갖는 Abstract Data Type이다.

 

우리는 구현의 방식을 여러개 가져갈 수 있는데, 이것은 Client의 입장에서 언제든 상황에 따라 다른 구현방식을 사용하게함으로서 유연하게 대처할 수 있도록 한다는 장점을 가져다준다.

 

1) Stack

 

Stack<T>의 기본 API는 다음과 같다.

 

void push(<T> item)

<T> pop()

boolean isEmpty()

 

Stack은 Linked List와 Array로 구현할 수 있다. 

Linked List의 경우, 삽입시에 Node Object를 생성하여 Linked List의 맨 앞에 연결하고, 삭제시에 제거 후 연결을 끊는다.

Stack의 경우, 삽입시에 배열의 끝에 추가하고, 삭제시에 제거한다.

만약 배열이 꽉찼을 경우 크기를 2배로 늘리는 전략을 사용할 수 있다. 또한, 배열의 1/4만큼만 남게된다면, 배열을 축소하여 공간을 확보할 수 있다. 

평균적인 성능의 경우 Linked List, Stack 둘 다 연산시 constant time이 걸린다.

메모리는 Stack을 쓰면 더 절약할 수 있다.

하지만, Stack의 경우 size를 doubling하여 item을 copy하는 순간에 시간이 오래걸리게 되고, 이것은 stack의 size가 클 수록 더 오랜시간이 걸리게 된다.

따라서, 매 순간마다 연산의 속도가 보장되어야 하는 경우에는 Linked List방식을, 그렇지 않은 경우에는 stack을 사용하는것이 일반적으로 좋다고 볼 수 있다.

 

2) Queue

 

Queue<T>의 기본 API는 다음과 같다.

 

void enqueue(<T> item)

<T> dequeue()

boolean isEmpty()

 

Queue 또한 Stack과 비슷하게 Linked List와 Array로 구현할 수 있고, 한가지 차이점은 자료구조의 양쪽 끝을 추적하여 한쪽에서는 삽입을 한쪽에서는 삭제를 한다는 것이다. Linked List, Array중 어떤걸 쓸지는 Stack에서 설명한 바와 동일하다.

 

3) Bag

 

Bag의 기본 API는 다음과 같다.

 

void add(<T> x)

Iterable<T> iterator() 

 

stack, queue와 유사하게 구현

 

3) Generics

Stack과 Queue의 경우 int, double, object1, car... 등등 item에 따라 모든 stack, queue를 구현하거나 그때 그때 casting하여 사용하는 것은 필치못한 상황(generics를 제공하지 않는 언어를 사용하는것 과 같은)이 아닌 경우 좋은 방법이 아니다. Casting할 때 만약 에러가 발생 한 경우, 이것은 실행시에만 발견 되므로 run-time error가 된다. 만약 Generics로 type parameter를 미리 준다면, 여기서 생기는 오류는 compile-time에 감지할 수 있다. 따라서, Client에게 전달되기 전에 미리 오류를 발견하고 수정할 수 있으며, 이는 큰 장점이다. 

JAVA의 경우 type parameter로 primitive type이 아닌 object type(wrapper)를 줌으로서, Object에서 제공하는 다양한 기능들을 쓸 수 있다. 예를 들어, JAVA의 iterable interface의 경우 item이 object type일 경우 iterator를 생성할 수 있는 interface를 제공한다. stack/queue를 iterable interface로 구현하면, stack/queue가 iterator가 되어, JAVA가 제공하는 더 간결한 코드를 생성할 수 있다.

ex)

for (String s : stack)

    StdOut.println(s) // 스택이 iterator이므로, 하나씩 꺼내서 출력가능

 

4) 응용

java의 경우 java.util.List API를 제공하며, java.util.ArrayList, java.util.LinkedList와 같은 library에서 이미 구현된 것들을 가지고 있다. 하지만, 이러한 구현된 것들이 항상 좋은 것들은 아니며, 그렇기 때문에 상황에 따라서 우리가 스스로 구현을 하는것이 좋다.

stack, queue는 다양한 상황에서 많이 쓰이고 있다. 대수연산을 구현하거나, 함수 호출과 같은 것들을 구현하는 것이 그 예다.