파이썬 문법2-자료구조

스택

선입후출 FILO
바닥부터 층층이 쌓여가는 구조
삽입/삭제: O(1)
조회:pop: O(1)

파이썬에서는 따로 스택을 지원하지 않기에 리스트를 사용한다. append로 삽입,pop으로 out됨

s=[]
s.append(1)
print(s[-1])   //파이썬은 -1번째 인덱스는 리스트 맨뒤를 가리키며				  
                  음수로 커질수록 역순으로 맨뒤에서부터 가리킴
s.pop(-1)

큐(Queue)

선입선출 FIFO :들어온 순서대로 나감
삽입/삭제: O(1)

파이썬에서 Queue를 지원하는데 이는 thread-safe를 지원하는 대신 deque에 비해 느리다. 코딩테스트에서는 multi-thread로 문제를 푸는 경우가 적으므로 주로 deque을 사용한다.
deque.append는 뒤에 값을 추가하고, deque.appendleft는 앞에 값을 추가한다.

from collections import deque

q=deque()
q.append(1)
q.append(2)

while len(q)>0:
	print(q.popleft())
    
//결과
1
2

우선순위 큐(Heap)

트리의 루트에 가장 큰값이 올 경우: 최대 힙
트리의 루트에 가장 작은 값이 올 경우: 최소 힙

• 파이썬에서 제공하는 heapq는 최소 힙이다.

  삽입/삭제: O(logN)

import heapq

hq=[]
heapq.heappush(hq,11)
heapq.heappush(hq,22)

while len(hq)>0:
	print(heapq.heappop(hq))
    
    
//결과
11
12

파이썬에도 PriorityQueue가 있다. 하지만 이도 마찬가지로 thread-safe를 지원하기에 상대적으로 느려 코딩테스트에서는 heapq를 대신 사용한다.

Map(dictionary)

key,value를 가짐, key는 중복 불가능
파이썬의 map은 hash로 구현되어 있다. 그래서
삽입/삭제: O(1)을 가진다.

m={}
m["hum"]=100
m["jini"]=99
m["jisoo"]=98

for k in m:
	print(k,m[k])
    
 //결과
 hum 100
 jini 99
 jisoo 98

Set(집합)

삽입/삭제: O(1) // 파이썬에서는 hash로 구현됨

중복을 허용하지 않고 저장한다.

s=set()
s.add(10)
s.add(10)
s.add(15)
s.add(15)
s.add(20)
//s에는 10,15,20만 저장됨
s.pop() //랜덤한 값이 빠짐 

랜덤한 값이 pop되기에 많이 사용되지는 않는다.