파이썬 자료구조

파이선 자료구조

---

자료구조는 대량의 데이터를 효율적으로 관리할 수 있도록 하는 데이터의 구조를 의미

데이터의 특성에 따라서, 체계적인 데이터 구조화가 필요하다.

 

대표적인 자료구조는 다음과 같음

배열 / 큐 / 스택 / 힙 / 해쉬테이블 / 링크드리스트

 

파이썬에는 대표적으로

List / Tuple / Set / Dictionary 를 지원하며, 대부분의 자료구조 구현가능

 

---

배열 (Array)

---

배열이란?

• 배열은 같은 종류의 데이터를 순차적으로 저장하는 자료구조 (파이썬의 리스트)
• index를 통해 직접 접근이 가능하다. (빠른접근가능)
• 데이터 추가와 삭제에 비용이 많이 듦
• 데이터 추가시 공간이 많이필요하며, 삭제 시 빈공간이 생겨 관리필요
• 길이조절이 어렵다는 단점이존재

 

​

---

큐 (Queue)

---

큐란?

• 먼저 넣은 데이터를 먼저꺼내는 데이터구조 (FIFO)

 

큐를 사용하는 두가지 방법

• 1. 파이썬에서 제공하는 queue 라이브러리 사용
  - import queue 
• 2. collections 라이브러리에서 제공하는 deque 사용
  - from collections import deque

 

첫번째 방법의 사용법

1. 일반적인 큐 

import queue

# 일반적인 큐 생성
obj = queue.Queue()

# 값 넣기
obj.put(1) # 1
obj.put(2) # 1 2 
obj.put(3) # 1 2 3

# 값 얻기
obj.get() # 1
obj.get() # 2
obj.get() # 3

2. LIFO 방식 큐 

# LIFO 방식 큐 생성  = Stack과 동일
obj = queue.LifoQueue()

# 값 넣기
obj.put(1) # 1
obj.put(2) # 2 1
obj.put(3) # 3 2 1

# 값 얻기
obj.get() # 3
obj.get() # 2
obj.get() # 1

 3. 우선순위 큐

# 우선순위 방식 큐 생성 
'''
데이터마다 우선순위를 지정해 정렬된 큐
우선순위 높은순으로 출력하게됨
'''
obj = queue.PriorityQueue() 
							
# 값 넣기 (우선순위,값)
obj.put((1,10))
obj.put((6,7))
obj.put((7,17))
obj.put((5,30))
obj.put((2,5))
obj.put((3,15))
obj.put((4,8))

# 값 얻기
obj.get() # 10
obj.get() # 5
obj.get() # 15
obj.get() # 8
obj.get() # 30
obj.get() # 7
obj.get() # 17

 

두번째 방법의 사용법

from collections import deque

de = deque([1,2,3,4,5])

# 리스트에서 사용하는 메소드가능
de.append(6) 		# deque([1,2,3,4,5,6])
de.pop() 	 		# 리턴값 6, de는 deque([1,2,3,4,5]) 가 된다.
de.extend([6,5,4])  # deque([1,2,3,4,5,6,5,4])
de.count(5) 		# 2
de.insert(3,11)     # deque([1,2,3,11,4,5,6,5,4])
de.index(3,2,7)     # 제일처음나오는 3값의 인덱스를리턴 (3,start,end)

# deque 추가기능 1. rotate
de.rotate(1) # 오른쪽으로 한칸씩 rotate
de.rotate(-1) # 왼쪽으로 한칸씩 rotate
de.rotate(2) # 오른쪽으로 두칸씩 rotate

# deque 추가기능 2. popleft()
de.popleft() # 맨앞의값을 삭제하고 리턴

# deque 추가기능 3. appendleft()
de.appendleft(x) # x값의 맨앞에 넣음

# deque 추가기능 4. extendleft(iterable)
de.extendleft(x) # x값을 맨앞에서 이어붙임 (순서역순)