1. 선형 자료구조와 비선형 자료구조

스택과 큐는 선형 자료구조이다.

선형 자료구조와 비선형 자료구조

자료구조는 크게 선형 구조와 비선형 구조로 나뉜다.

• 선형 구조: 자료를 구성하는 원소들을 하나씩 순차적으로 나열시킨 형태이다. 자료들 간의 앞, 뒤 관계가 1:1 관계이다. (ex, 배열, 리스트, 스택, 큐)

• 비선형 구조: 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 형태이다. 자료들 간의 앞, 뒤 관계가 1:N 또는 N:N이다. (ex, 트리, 그래프)

2. Stack

• 스택은 가장 나중에 들어간 원소가 먼저 나오는 구조이다. (LIFO: Last in First Out)

• LinkedList를 이용한 구현과 ArrayList를 이용한 구현이 있다.

• 조회: Top에 있는 원소를 조회할 때는 O(1)의 시간 복잡도를 갖는다. 하지만 Top 원소가 아닌 다른 특정 데이터를 찾고자 할 때는 특정 데이터를 찾을 때까지 수행해야 하므로 O(N)이다.

• 삽입: LinkedList를 이용한 구현에서는, 단순히 Top 원소를 새 원소의 next로 연결시켜주고 head의 포인터가 새로운 원소를 가리키게 하면 되기 때문에 O(1)이다. ArrayList를 이용한 구현에서도, 특정 상황(Dynamic array의 팽창)을 제외하고는 O(1)이다.

• 삭제: LinkedList와 ArrayList 모두 O(1)이다.

3. Queue

• 큐는 가장 먼저 들어간 원소가 먼저 나오는 구조이다. (FIFO: First in First out)

• LinkedList를 이용한 구현과 ArrayList를 이용한 구현이 있다.

• 조회: 가장 끝에 있는 원소를 조회하므로 O(1)이다. 하지만 스택과 마찬가지로 가장 끝의 원소가 아닌 특정 데이터를 찾고자 할 때는 특정 데이터를 찾을 때까지 수행해야 하므로 O(N)이다.

• 삽입: LinkedList와 ArrayList 모두 O(1)이다.

• 삭제 : LinkedList와 ArrayList 모두 O(1)이다.

4. 정리

스택과 큐 모두 ArrayList를 이용하거나 LinkedList를 이용하여 구현할 수 있다. 단, ArrayList를 사용하는 경우에는 Dynamic array의 팽창을 고려해야 하기 때문에 최악의 경우에는 느리지만, 전반적인 성능이 좋다. 반대로 LinkedList를 사용하는 경우에는 일관된 성능(O(1))을 보여주지만, 메모리 할당에 들어가는 추가적인 비용 때문에 런타임 성능이 낮을 수 있다. (LinkedList는 노드 구조를 유지하는데 추가적인 메모리 사용량이 필요하다.)