스택과 큐

JAVA/자료구조

도전하는일반인 2021. 10. 15. 08:01

들어가기 전에

배열에 대해 살펴보도록 하겠습니다.

학습 목표

배열과 연결 리스트의 차이점을 이해할 수 있습니다.

핵심 단어

배열에는 순서가 있습니다. 그래서 첫 부분을 제거하거나 추가하려면, 요소들을 하나씩 뒤로 옮겨야 하고 시간 복잡도는 O(n)O(n) 입니다. 스택과 큐의 과정이 비효율적이기 때문에 스택과 큐에서 기본적인 배열을 사용하지 않습니다.

연결 리스트에서는 배열 맨 앞을 가리키는 head 포인터를 사용합니다. 그래서 리스트의 첫 부분을 제거하거나 추가하는 과정의 시간 복잡도가 상수입니다. 더 효율적인 알고리즘인 연결 리스트는 스택과 큐를 하는 데 사용합니다.

배열은 연결 리스트보다 전형적으로 빠르고 메모리도 덜 차지합니다. 그러나 배열은 크기가 정해져 있습니다.

생각해보기

1) 스택과 큐를 배열에 구현한다면 시간 복잡도는 어떻게 되나요?

나의 생각:

스택) 스택이란 후입 선출의 특성을 가지고 있다. 마지막에 넣은것을 먼저 뺀다는 뜻이다.

addLast removeLast는 상수이기때문에 스택은 O(1)과 O(1) 이다.

큐) 큐란 선입 선출의 특성을 가지고 있다. 처음 넣은것을 먼저 뺀다는 뜻이다.

addFirst removeLast를 사용하기 때문에 O(n)과 O(1)이다.