스택과 큐

스택

배열을 이용해 스택을 구현하려면 배열 뒤쪽을 이용해 addFirst와 removeFirst를 해야합니다.
그러나 둘다 시간복잡도는 $O(n)$입니다.
이는 비효율적이기 때문에 시간복잡도가 $O(1 )$인 addLast와 removeLast만 가능합니다.

큐

배열로 큐를 구현하는 경우에 만약 addLast와 removeFirst를 쓴다면 addLast는 시간복잡도가 $O(1)$이고 removeFirst를 $O(n)$이고 입니다.
이것 또한 비효율적입니다.

addFirst와 removeLast도 마찬가지입니다.

그래서 스택과 큐에서는 기본적인 배열을 사용하지 않습니다.

리스트에서는 배열 맨 앞을 가리키는 head 포인터를 사용해첫 부분을 제거하거나 추가하는 과정의 시간 복잡도가 $O(1)$입니다.

그래서 리스트는 스택과 큐를 하는 데 사용하는데 효율적인 알고리즘이 될 수 있습니다.

배열과 LinkedList비교

배열은 리스트보다 빠르고 메모리도 덜 차지합니다.
그러나 배열은 크기가 고정되어있기때문에 배열이 차게되면 배열의 크기를 늘리고, 내용을 옮겨야합니다.
그래서 배열이 처음 부터 적절한 크기로 만들지 않는 경우, 배열의 크기를 늘리고, 내용을 옮기는 과정을 반복하면서 리스트보다 속도가 느려질 수가 있습니다.

하지만 리스트는 크기가 정해져있지 않습니다.
하지만 단점은 느리고 메모리가 많이 필요합니다.