[자료구조] 12. 다중 스택과 큐

1. 다중 스택(Multiple Stack)

• 스택의 오버플로우 방지를 위해 여러 개의 스택을 하나의 기억 공간에 저장하는 구조

 

구현 방법

• 2개의 스택을 연결: 배열 양쪽에서 각각의 스택이 증가

• n개의 스택을 연결: 사용 가능한 기억 공간을 균등 또는 가변적으로 분할

 

삽입 및 삭제 연산

• 삽입: 특정 스택이 가득 찼는지 확인 후 데이터 추가

• 삭제: 스택이 비어있는지 확인 후 top 데이터를 제거

 

 

 

2. 다중 큐(Multiple Queue)

• 프로세스 효율적 관리를 위해 여러 개의 큐를 연결하여 운영

 

운영 방식

• 고정 우선순위 방식: 프로세스가 종료될 때까지 우선순위 유지

• 변동 우선순위 방식: 실행 중 우선순위 변경 가능

• 반전 우선순위 방식: 낮은 우선순위를 높은 우선순위로 변경

• 대기 상태 큐: 같은 입출력을 요구하는 프로세스를 모아 운영

 

 

 

3. 우선순위 큐(Priority Queue)

• 데이터의 입력 순서와 관계없이 우선순위가 높은 데이터가 먼저 출력

 

구현 방법

• 배열 기반: 간단하지만 삽입·삭제 시 데이터 이동이 필요

• 연결 리스트 기반: 이동은 없지만 탐색이 필요하여 성능 저하 가능

• 힙(Heap) 기반: 완전 이진 트리 구조로 삽입·삭제 연산의 시간 복잡도가 O(log n)

 

 

 

4. 힙(Heap)

• 완전 이진 트리를 기반으로 최대값 또는 최소값을 빠르게 찾을 수 있는 자료구조

 

종류

• 최대힙(Max Heap): 부모 노드가 자식보다 크거나 같음, 루트에 최대값 위치

• 최소힙(Min Heap): 부모 노드가 자식보다 작거나 같음, 루트에 최소값 위치

 

삽입 연산

• 새로운 노드를 추가한 후 부모와 비교하여 조건이 만족될 때까지 자리 변경

---

이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.