TIL_221017 자료구조

핵심단어

추상자료형, 파이썬 내장함수, Data Structure

학습목표

• ADT(추상자료형) 연결리스트, 큐, 스택의 설계에 대해 익히기
• 레퍼런스 : urclass 참고하기

WARM UP

스택 : 배열이 수직으로, LiFo (라스트인, 펄스트 아웃)
큐 : FiFo (펄스트인, 펄스트 아웃)

ADT(추상자료형)의 시작

• linked-list ADT, Stack ADT, Queue ADT

• ADT를 활용하는 이유
  • 데이터처리를 위한 자료형 존재
  • 파이썬에서 프로그래밍을 위한 도구들인 기본자료형(숫자,문자열,리스트,딕셔너리 등)에 대해 배움
  • ADT는 추상적으로 필요한 기능을 나열한 일종의 명세서(로직)

    • ADT는 기본자료형(리스트,숫자,문자열)을 활용하여 사용자에 의해 구현됨

      
      
• ABSTRACT
  • abstract는 소프트웨어가 발전하면서 프로그램의 크기나 복잡도가 같이 증가하였고, 프로그램의 핵심 부분을 간단하게 설명하기 위해 생겨남

연결리스트

자료구조와 연결리스트

• 연결리스트는 말 그대로 리스트들을 '연결'해준다.
  -
  • 연결은 프로그래밍에서의 참조의 기능으로 구현되고, 연결리스트는 리스트의 길이를 별도로 지정해줄 필요가 없다
  • 또한 인덱스 지정이 필요없이 연결되는 구조
• 배열은 요소를 직접 접근하여 저장하고 인덱스 활용
• 연결리스트의 각 요소는 참조하는 노드에 저장됨
  • 각 노드는 연결리스트의 다음 노드에 대해 참조를 한다
    • 참조기호 : .으로 지칭
      • 삽입, 할당기호 : =로 표현

코드 구현은 링크 참조 (하 오늘 넘 뿌듯하다!)

파이썬을 활용한 큐와 스택

큐

• 큐는 항목을 fifo(선입선출) 순서로 저장하는 자료 구조
  • 마치 마트의 계산줄
  • 먼저 줄서면 먼저 계산이 끝난다
• deque : double-ended-queue의 줄임말
  • 큐에서 양방향으로 데이터를 처리
  • double은 자료구조에서 양방향을 의미
• Queue 클래스의 경우, 먼저 init메서드를 정의해야함
  - 그리고 그 메서드에서 앞과 뒤의 인스턴스변수를 초기화해야함

 class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

• 큐의 시간, 공간복잡도
  • Enqueue(대기열에 넣기)
    데이터를 큐에 추가하면 (큐의 rear에 추가) O(1) 시간이 걸림
  • Dequeue(대기열에서 빼기)
    데이터를 큐에서 빼면 (큐의 front에서 제거) O(1) 시간이 걸림

연결리스트를 이용해 큐와 스택을 구현하는 이유

• 연결리스트는 파이썬에 없는 자료구조, 사용하려면 직접 클래스로 구현하여 사용해야 함

• 연결리스트를 구현하고 이해하기 위해서는 해당 자료구조를 많이 사용해야함

• 클래스에서 enqueue를 통해 값을 넣어주고, dequeue를 통해 값을 제거해주는데

• enqueue에 새로운 노드의 저장공간(변수)를 만들어주고, 그 저장공간에 노드를 넣어주는 개념

• dequeue에 삭제할 노드를 위한 저장공간을 만들고, 그 저장공간에 삭제 노드를 넣어주는 개념
  (렉쳐노트 그림 참고하면 이해력 올라감)

스택

• 스택 : ex) 윈도우 프로그램(컴퓨터 종료 시, 가장 먼저 운영체제가 구동되고 가장 마지막으로 종료됨)

나머지 내용은 코드 구현에 설명포함