Stack, Queue, Heap

한혜성·2022년 4월 21일
0

자료구조

목록 보기
2/4

Stack

  • stack : 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조
  • 특징
    • 배열과 달리 상수 시간에 i 번째 항목에 접근 불가
    • 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능
    • 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요 없음
  • 연산
    • 가장 최근에 스택에 추가한 항목 = 가장 먼저 제거될 항목
    • push(E item) : 해당 item을 top에 삽입
    • pop : top에 있는 item 삭제O, 해당 item 반환
    • peek : top에 있는 item 삭제 X, 해당 item 반환
    • isEmpty : stack이 비어있으면 true, 그렇지 않으면 false 반환
    • search(Object O) : 해당 Object의 위치 반환, top 위치는 1, 해당 Object가 없으면 -1 반환, O(n)
  • 사용 방법
    • 웹 브라우저 방문 기록(뒤로 가기)
    • 실행 취소
    • 역순 문자열 만들기
    • 수식의 괄호 검사
    • 후위 표기법 계산
    • DFS

Queue

  • Queue : 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out)형식의 자료구조

  • Java Collection에서 Queue는 인터페이스이다. 이를 구현하고 있는 우선순위큐 등을 사용할 수 있다.

  • 연산

    • 가장 처음에 추가한 항목 = 가장 먼저 나오게 될 항목
    • java 라이브러리 Queue 관련 메서드
      • 수행이 실패했을 때 exception 발생 : add, element, remove
        • add : 해당 item을 queue에 삽입,
          ​ 삽입에 성공하면 true 반환, 공간이 없으면 예외(IllegalStateException)발생
        • element : queue의 head에 있는 item 삭제하지 않고 반환, queue가 비어있다면 예외발생
        • remove : queue의 head에 있는 item 삭제하고 반환, queue가 비어있다면 예외발생
      • 수행이 실패했을 때 null 또는 false 반환 : offer, peek, poll
        • offer : queue에 삽입, 성공 시 true 반환, 실패 시 false 반환
        • poll : 리스트의 첫 번째 항목 제거
        • peek : 큐에서 가장 위에 있는 항목 반환
        • isEmpty : 큐가 비어있을 때 true 반환
  • 사용 방법

    • BFS
    • 우선순위가 같은 작업 예약(인쇄 대기열)
    • 선입 선출이 필요한 대기열(티켓 카운터)
    • 콜센터 고객 대기시간
    • 윈도우 시스템의 메시지 처리기
    • 프로세스 관리 : 프로세스는 일반적으로 여러개가 한번에 수행 -> 순서 필요
      • Job queue, Ready queue, Device queue

Heap

  • heap : 완전 이진 트리를 기초로 하며 우선순위 큐를 위한 자료구조

    • 완전 이진 트리 : 마지막을 제외한 모든 노드에서 자식들이 꽉 채워져 있는 이진 트리
    • 최대힙(Max Heap) : 부모 노드 >= 자식 노드
    • 최소힙(Min Heap) : 자식 노드 >= 부모 노드
    • 항상 반정렬 상태(느슨한 정렬 상태) 유지
    • 중복값 허용
    • 왼쪽 자식 : (2i) 번째 / 오른쪽 : 2i +1
  • 연산

    • 재구조화(heapify) : 삽입, 삭제로 인해 최대힙의 조건이 깨질 수 있으므로 재구조화 필요
      • 삽입, 삭제 모두 연산 자체는 O(1)로 작동하지만 heapify 과정을 거치기 때문에 O(logN)의 시간복잡도를 가짐
      • 삽입 - 가장 왼쪽 밑에 새로운 노드로 삽입됨, upHeap()이라는 알고리즘에 의해 정렬
      • 삭제 - 큐이기에 항상 루트 노드에서 삭제가 이루어짐, downHeap()을 통해 정렬
  • 응용

    • 데이터의 우선순위를 다루는 상황
    • 실시간 급상승 검색어 제공


참고자료
https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html
https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html
https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap
https://velog.io/@junhok82/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap

profile
백엔드하고 싶은 사람 소오오온~~

0개의 댓글