스택(Stack), 큐(Queue), 힙(Heap) 에 대해서

자료구조 알고리즘을 하다보면 스택, 힙, 큐에 대해서 많이 얘기를 들어봤을텐데 오늘 포스팅에서는 하나씩 설명을 해보려고 한다.

 

스택

• 선형 자료구조
• Last In First out(LIFO) 구조
  
• 스택 특징
  
  • 같은 구조의 같은 크기의 자료를 정해진 방향으로만 쌓을 수 있음
  • top으로 정한 곳을 통해서만 접근 가능(top이란 가장 쌓아둔 윗부분)
  • 삭제는 top을 통해서만 가능
• 스택 연산
  • 삭제 (pop()) : 스택에서 가장 위에 있는 항목을 제거
  • 삽입 (push(item)) : item 하나를 스택의 가장 윗부분에 추가
  • 읽기 (peek()) : 스택의 가장 위에 있는 항목을 반환
• 스택 포인터(SP)
  • push나 pop을 할 때 해당 값의 위치를 알고 있어야 하는데 스택 포인터가 위치를 기억하고 처음 기본값은 -1
• 활용 예시
  • 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여줌
  • 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력
  • 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소
  • 후위 표기법 계산
  • 재귀함수(recursive call)

큐

• 선형 자료구조
• FIrst In First Out(FIFO) 구조
• Java Collection에서 Queue는 인터페이스다.
  
  
• 큐의 특징
  • 가장 첫 원소를 front, 끝 원소를 rear
  • 가장 첫 원소와 끝 원소로만 접근 가능
• 큐의 연산
  • 삽입 (Enqueue()) : 큐 맨 뒤에 어떠한 요소를 추가
  • 삭제 (Dequeue()) : 큐 맨 앞쪽의 요소를 삭제
  • 읽기 (peek()) : front에 위치한 데이터를 읽음
• front / rear
  • 데이터를 넣고 뺄 때 해당 값의 위치를 기억해야 함(스택 포인터와 같은 역할)
  • front : 큐의 맨 앞의 위치(인덱스)를 본다.
  • rear : 큐의 맨 뒤의 위치(인덱스)를 본다.
• 선형 큐와 원형 큐로 나뉘어 짐
  • 선형 큐
    • 큐에 데이터가 꽉 차면 데이터 더이상 추가 불가
    • 선형 큐에서 삽입 및 삭제를 반복하다 보면, rear가 맨 마지막 인덱스를 가리키고, 앞에는 비어 있을 수 있지만 이를 꽉 찼다고 인식함
    • 이 현상 때문에 원형 큐가 나옴
  • 원형 큐
    • 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주함
    • 초기 공백 상태일 때 front와 rear가 0
    • 공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둠(사이즈+1)
    • 데이터 추가 시 rear가, 삭제 시 front가 1칸 움직임
• 큐 활용 예시
  • 대기 번호표
  • 물품 진열
  • BFS 구현
  • 프린터 출력 처리
  • 콜센터 고객 대기시간

힙

• 완전 이진트리의 일종 (여러 값 중, 최댓값과 최솟값을 빠르게 찾아내도록 만들어진 자료구조)
• 우선순위 큐를 위해 만들어진 자료구조
• 일종의 트리로 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 빅오 : O(logn)
•  
• 우선 순위 큐
  • 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 out
  • CPU 작업 스케줄링, 시뮬레이션 시스템에서 사용
• 힙 종류
  • 최대 힙(max heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
    • key(부모 노드) ≥ key(자식 노드)
  • 최소 힙(min heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
    • key(부모 노드) ≤ key(자식 노드)
• 힙 특징
  • 힙을 저장하는 표준적인 자료구조는 배열
  • 중복 값을 허용
  • 반 정렬 상태를 유지
• 힙 연산
  • 삽입
    • 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입
    • 새로운 노드를 부모 노드들과 교환
  • 삭제
    • 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제됨 (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것)
    • 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
    • 힙을 재구성