Stack과 Queue 구현, 배열과 링크드 리스트 중 어떤 것을 이용할까?

Summary

Stack : 둘 다 가능

Queue: 리스트를 이용하는 것이 일반적.

Stack & Queue

1. Stack
   1. Array와 LinkedList 모두 구현 가능하다.
   2. Array
      1. 장점
         1. 메모리에 연속적으로 할당되는 특징 덕분에 캐시 지역성을 이용한 더 빠른 접근이 가능하다.
      2. 단점
         1. 사이즈가 제한되어 있다. 고정 크기 배열 경우 사이즈를 늘리기가 불가능하고, 유동 크기 배열의 경우 사이즈가 한계에 다다르면 어레이를 (일반적으로) 두배 크기로 늘리고, 기존의 요소들을 모두 복사해야하는 작업이 필요하다.
   3. LinkedList
      1. 장점
         1. 사이즈에 제한 받지 않는다.
      2. 단점
         1. 배열과 달리 요소가 연속적으로 할당되지 않아 비교적 느리다.
         2. 포인터를 위한 추가적인 메모리 공간이 필요하다.
2. Queue
   1. LinkedList로 구현하는게 이상적이다.
      1. FIFO 이기 때문에 앞선 인덱스의 요소가 제거될 경우 모든 뒤의 요소들을 하나씩 앞으로 당겨주어야 한다. 이로 인해 배열을 사용하는 것은 비효율적이다. 포인터를 바꾸면 되는 LinkedList를 사용하는 것이 효율적이다.