[Python] 05 Python Data Structure

01 Data Structure

01-1 Stack

• 스택 Stack
  • Last In First Out (LIFO)
    • 나중에 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조
• 스택 관련 메서드
  • S.push(e): element e를 stack S의 맨 위에 추가
  • S.pop(): stack S의 맨 위 element를 삭제하고 return
  • S.top(): stack S의 맨 위 element를 삭제하지 않고 그 주소를 return
  • S.is_empty(): stack S에 element가 없는 경우 true를 return
  • len(S): stack S의 element의 개수를 return
• Stack with list object

S = [1, 2, 3, 4, 5]
S.append(10)      # push. S = [1, 2, 3, 4, 5, 10]
S.append(20)      # push. S = [1, 2, 3, 4, 5, 10, 20]
S.pop()           # pop. 20 출력
S.pop()           # pop. 10 출력

01-2 Queue

• 큐 Queue
  • First In First Out (FIFO)
    • 먼저 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조
  • Stack과 반대되는 개념
• 큐 관련 메서드
  • Q.enqueue(e): queue Q의 맨 뒤에 element e를 추가
  • Q.dequeue(): queue Q의 맨 첫 번째 element를 삭제하고 return
  • Q.first(): queue Q의 맨 첫 번째 element를 삭제하지 않고 그 주소를 return
  • Q.is_empty(): queue Q에 element가 없는 경우 true를 return
  • len(Q): queue Q의 element의 개수를 return
• Queue with list object

Q = [1, 2, 3, 4, 5]
Q.append(10)      # enqueue. Q = [1, 2, 3, 4, 5, 10]
Q.append(20)      # enqueue. Q = [1, 2, 3, 4, 5, 10, 20]
Q.pop(0)           # dequeue. 1 출력
Q.pop(0)           # dequeue. 2 출력

01-3 Tuple

• 튜플 Tuple
  • 값의 변경이 불가능한 리스트
  • 프로그램이 작동하는 동안 변경되지 않을 데이터를 저장하기 위해 사용
• 튜플과 리스트의 공통점 / 차이점
  • 공통점
    • 모든 자료형을 요소로 사용 가능
    • 순서가 있는 자료형으로, indexing / slicing 가능
    • 덧셈 및 곱셈 연산 가능
  • 차이점

    리스트	튜플
    []로 표현	()로 표현
    요소의 생성, 삭제, 변경 가능	요소의 생성, 삭제, 변경 불가
    요소가 하나일 때는 [1]	요소가 하나일 때에는 1, / (1,) (반드시 콤마 필요)

• 튜플 요소의 값 삭제 및 변경 시도 → type error
• 튜플의 인덱싱과 슬라이싱
  • 인덱싱 → 요소값 반환
  • 슬라이싱 → 튜플 형태로 반환
• 튜플 관련 함수
  • 리스트의 연산, 인덱싱, 슬라이싱 등을 동일하게 사용
  • 튜플은 immutable 객체이기 때문에 insert, append, extend x

01-4 Dict

• 사전 dictionary
  • 데이터를 저장할 때 데이터들(value)을 구분 지을 수 있는 고유한 값(key)을 함께 저장
  • 다른 언어에서는 hash table이라고 함
• key의 조건
  • 고유한 값이어야 함; 중복되지 않아야 함
  • immutable (hashable) 객체만 들어갈 수 있음
    • ex. 문자열, 단일 숫자, 튜플
• 딕셔너리 추가와 삭제
  • 딕셔너리 key & value 추가
  • 딕셔너리 삭제: del dic[key]
• 딕셔너리 관련 함수
  • x.keys()
  • x.values()
  • x.items()
  • x.clear()
  • x.get(a)
  • a in x

01-5 Set

• 집합 Set
  • 중복을 허용하지 않음
  • 순서가 없음 → 인덱싱 / 슬라이싱 불가
• cf. 리스트 vs 튜플 vs 딕셔너리 vs 집합

  	순서	인덱싱/슬라이싱
  리스트	o	o
  튜플	o	o
  딕셔너리	입력 순서대로 만들어짐	x
  집합	x	x

• 수학에서의 집합 연산: 교집합, 합집합, 차집합
  • 교집합: & / .intersection()
  • 합집합: | / .union()
  • 차집합: - / .difference()
• 집합 관련 함수
  • x.add()
  • x.update(): 값 여러개 추가
  • x.remove()
    • del로 list처럼 item deletion은 불가 (set 전체 삭제만 가능)
    cf. del의 쓰임
    • list: item deletion) del lst[2]
    • dictionary: item deletion) del dic[key]
    • tuple: tuple deletion) del tpl
    • set: set deletion) del set

02 Collections

• collections
  • list, tuple, dict 등의 자료형을 다루기 위한 python built-in module

02-1 Deque

• Stack과 Queue를 지원하는 모듈
• list에 비해 ‘효율적’인 자료 저장 방식을 지원
  • 메모리를 적게 사용
  • 속도가 빠름
• rotate, reverse 등 linked list의 특성을 지원
• 기존 list 형태의 함수를 모두 지원

02-2 Defaultdict

• dict type의 default value를 지정해둠으로써, 신규 key가 value 없이 생성되었을 때 default value를 부여

from collections import defaultdict
d = defaultdict(object)     # default dictionary를 생성
d = defaultdict(lambda: 0)  # default value를 0으로 설정
print(d["first"])           # 0

02-3 Counter

• sequence type 내의 data element들의 개수를 dict 형태로 반환

from collections import Counter

# string
c = Counter()
c = Counter("gallahad")     
print(c)                    # Counter({'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1})

# dictionary
c = Counter({"red":4, "blue":2})
print(c)                    # Counter({'red': 4, 'blue': 2})
print(list(c.elements()))   # ['red', 'red', 'red', 'red', 'blue', 'blue']

# keyword parameter
c = Counter(cats=4, dogs=8)
print(c)                    # Counter({'dogs': 8, 'cats': 4})
print(list(c.elements()))   # ['cats', 'cats', 'cats', 'cats', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs']

02-4 Namedtuple

• ‘Factory Function for Tuples with Named Fields’
• Data 구조체를 Tuple 형태로 저장하는 방법
• 정의 방식
  • 리스트로 구분
    • Point = namedtuple('Point', ['x', 'y'])
  • 띄어쓰기로 구분
    • Point = namedtuple('Point', 'x y')
  • 콤마로 구분
    • Point = namedtuple('Point', 'x, y')
  • 같은 key가 중복되거나 예약어를 사용하는 경우, rename=True 사용
    • Point = namedtuple('Point', 'x y x class', rename=True)
  • Dictionary를 unpacking
    • temp_dict = {'x': 40, 'y': 30}
    • p1 = Point(**temp_dict)

from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p = Point(11, y=22)     
p[0] + p[1]             # 33
x, y = p                
x, y                    # (11, 22)
p.x + p.y               # 33
p                       # Point(x=11, y=22)

 

 

• reference
  • https://zzsza.github.io/development/2020/07/05/python-namedtuple/
  • https://wikidocs.net/84392