[자료구조] 스택, 큐, 힙 차이 (+ 배열과 연결 리스트를 이용한 구현 차이)

목차

• 스택 개념과 활용
• 큐 개념과 활용
• 힙 개념과 활용
• 배열과 연결리스트를 이용한 구현 차이

 

---

1. 스택

스택은 LIFO 방식의 자료구조로, 나중에 들어온 원소가 가장 먼저 제거된다. 리스트의 한쪽 끝에서 삽입, 삭제가 이뤄지며, 가장 마지막으로 실행한 동작을 가져와야 할 때 사용된다. 스택에서 가장 위쪽에 있는 값을 top이라고 하며, 원소 삽입, 삭제 시에 top을 가리키는 값이 변화된다.

 

(사용 예시)

• 웹사이트 방문 기록
• ctrl+z 실행 취소
• 함수 호출

(관련 함수 - 자바)

• push(x) : 스택의 가장 위쪽에 x라는 원소 삽입
• pop() : 스택의 가장 위쪽에 원소 삭제
• peek() : 스택의 가장 위쪽에 원소 읽기
• isEmpty() : 스택이 비어있으면 true, 비어있지 않으면 false 반환
• size() : 스택 사이즈 반환

 

https://www.geeksforgeeks.org/stack-meaning-in-dsa/

 

---

2. 큐

큐는 FIFO 방식의 자료구조로, 가장 처음에 들어온 원소가 가장 먼저 제거된다. 리스트의 한쪽에서 삽입이 이뤄지면, 그 반대쪽에서 삭제가 이뤄진다. 큐에서 삭제가 이뤄지는 쪽을 front(혹은 head)라고 부르며, 삽입이 이뤄지는 쪽을 read(혹은 tail)이라고 한다.

 

(사용 예시)

• 프로세스 관리
• 작업 대기

(관련 함수 - 자바)

• add(x) : 큐의 가장 뒤쪽에 x라는 원소 삽입
• poll() : 큐의 가장 앞쪽 원소 삭제
• peek() : 큐의 가장 앞쪽 원소 읽기
• isEmpty() : 큐가 비어있으면 true 반환, 비어있지 않으면 false 반환
• size() : 큐 사이즈 반환

 

 

---

3. 힙

힙은 완전 이진 트리의 일종으로 여러 값들 중에서 최솟값이나 최댓값을 빠르게 찾을 수 있도록 만들어진 자료구조이다. 최솟값 혹은 최댓값을 찾을 때 배열을 이용하면 O(n)만큼의 시간일 걸린다. 하지만 힙(트리)을 이용하면 O(log(n))만큼의 시간이 걸린다.

 

(사용 예시)

• 우선순위 큐
• 운영체제 작업 스케줄링

(관련 함수 - 자바)

• add(x) : 힙에 x라는 원소 삽입
• pop() : 힙에서 제일 앞쪽 원소 삭제
• poll() : 힙에서 제일 앞쪽 원소 읽기
• isEmpty() : 힙이 비어있으면 true 반환, 비어있지 않으면 false 반환
• size() : 힙 사이즈 반환

 

https://www.geeksforgeeks.org/heap-data-structure/

 

---

4. 배열과 연결 리스트를 이용한 구현 차이

스택과 큐, 힙은 배열 혹은 연결 리스트로 구현할 수 있다.

 

배열은 사용 시 고정적인 크기를 할당해주어야 하며, 배열에 저장된 순서와 실제 메모리에 저장된 순서가 동일하다. 컴퓨터는 이전에 참조했던 메모리와 그 주변 메모리에 자주 접근하는 참조 지역성의 원리를 지니고 있다. 이 원리와 함께 배열은 메모리에 순차적으로 저장되어 있다는 특징으로 배열이 캐시에 존재할 가능성이 커진다. 따라서 배열에 접근하고자 할 때 속도가 빠르다는 장점을 가진다.

 

연결 리스트는 가변적인 크기를 가지며, 데이터가 메모리 상에서 연속적으로 존재하지는 않는다. 다음 노드가 위치한 주소를 가지고 있기 때문에, 데이터에 대한 추가 및 삭제가 쉽고 메모리를 낭비하지 않는다.

 

결과적으로 배열을 이용해 스택, 큐, 힙을 구현하게 되면 원하는 요소에 빠르게 접근할 수 있다. 하지만 고정적인 메모리로 인해 추가 공간이 필요할 수도 있다는 단점을 가진다. 연결 리스트를 이용해 스택, 큐, 힙을 구현하게 되면 메모리 사용에 대해 자유로워진다. 하지만 배열을 사용해 구현했을 때보다 속도가 느리다.

 

	배열	연결 리스트
자료형	Arrays	LinkedList
메모리 크기	고정적	가변적
메모리 주소	순차적 주소	랜덤 주소
메모리 할당	컴파일 시 정적 메모리 할당	런타임 시 동적 메모리 할당
접근	O(1)	O(n)
검색	O(n)	O(n)
추가	추가하려는 위치가 맨 뒤라면 O(1) 그 외에는 O(n)	추가하려는 위치가 맨 앞이라면 O(1) 그 외에는 O(n)
삭제	삭제하려는 위치가 맨 뒤라면 O(1) 그 외에는 O(n)	삭제하려는 위치가 맨 앞이라면 O(1) 그 외에는 O(n)