[Python]Stack, Queue, Heap, Dictionary, Set

1. Stack

• 삽입/삭제: O(1)
• FILO(First In Last Out), LIFO(Last In First Out)
• Python에서는 List로 구현된다.

a = []
a.append(111)
a.append(222)
a.append(333)
print("size:", len(a))
while len(a) > 0:
	print(a[-1])
    a.pop()  # a.pop(-1)과 동일하다.

2. Queue

• 삽입/삭제: O(1)

from collections import deque

b = deque()
b.append(111)
b.append(222)
b.append(333)
print("size:", len(b))
while len(b) > 0:
	print(b.popleft())

3. Priority Queue (Heap, 우선순위 큐)

• 삽입/삭제: O(logN)
• C++는 max-heap을 제공하지만, Python에서는 min-heap을 제공한다.
  (root node에 가장 작은 값이 위치한다.)

import heapq as hq

pq = []
hq.heappush(pq, 456)
hq.heappush(pq, 123)
hq.heappush(pq, 789)
print("size:", len(pq))
while len(pq) > 0:
	print(hq.heappop(pq))

4. Dictionary

• Key는 중복이 될 수 없지만, Value는 중복된 값이 올 수 있다.
• 삽입/삭제: O(1)

m = {}
m["a"] = 10
m["b"] = 30
m["c"] = 50
print("size:", len(m))
for i in m:
	print(i, m[i])

5. Set (집합)

• 중복된 값은 하나만 받는다.
• 삽입/삭제: O(1)

s = set()
s.add(10)
s.add(20)
s.add(40)
s.add(10)
s.add(20)
s.add(40)
s.pop()

을 수행시 앞에서 다룬 자료구조와 다르게 정해진 위치가 아닌 Random값이 pop()된다. (그러므로 쓸일이 없다.)
s.remove(20)을 사용한다.

s = set()
s.add(456)
s.add(221)
s.add(211)
s.add(241)
s.add(212)
s.add(221)
print("size:", len(s))
for i in s:
	print(i)