자료구조_스택, 큐

 

 

 

 

[스택(Stack)]

▶ 스택은 한쪽 끝에서만 자료의 삽입(push)와 삭제(pop)이 일어나는 자료구조

 

▶ 파이썬에서는 리스트(list)를 활용해 스택을 구현하기 때문에 스택을 위한 모듈이 따로 필요하지 않다.

 

▶ 선입후출(FILO) (ex : 박스 쌓기)

 

 

# 리스트를 활용해 스택을 생성
stack = []

# 자료의 삽입(push)
# append() 메서드를 활용
stack.append(4) # [4]
stack.append(1) # [4, 1]
stack.append(3) # [4, 1, 3]

# 자료의 삭제(pop)
# pop()메서드를 활용
stack.pop() # 3
stack.pop() # 1
stack.pop() # 4

stack # []

# 스택의 최상단 자료의 확인
# 리스트 인덱싱[-1]을 활용한다.
stack.append(1) # [1]
stack[-1] # 1
stack.append(3) # [1,3]
stack[-1] # 3

# 스택이 비어있는지 확인
# 조건문을 활용해 스택이 비어있는지 확인 가능
if stack:
    # 스택이 비어있지 않은 경우
    pass
else:
    # 스택이 비어있는 경우
    pass

# 스택의 크기 확인
# len(stack)으로 확인
stack = [1, 2, 3, 4] # [1, 2, 3, 4]
len(stack) # 4
stack.pop() # 4
len(stack) # 3

 

 

[큐(Queue)]

▶ 선입선출(FIFO) : 먼저 집어넣은 자료가 먼저 나옴(=웨이팅)

 

▶ 파이썬에서 큐를 이용하는 방법

1) 리스트 자료형 사용 : 리스트를 사용하면 큐에 데이터를 넣는 enqueue를 append()메소드, 데이터를 빼는 dequeue를 pop(0)으로 구현할 수 있다. 다만 리스트의 pop(0)은 O(n)의 시간복잡도를 가지기 때문에 큐를 구현할 때는 더 효율적인 방법을 사용한다.

2) Queue 사용 : queue 모듈의 Queue는 데이터를 단방향에서 추가하고 제거할 수 있는 자료구조이다. enqueue를 위해서는 put()메소드를, dequeue를 위해서는 get()메소드를 사용한다. get()메소드는 리스트의 pop()과 다르게 시간복잡도가 O(1)이므로 리스트보다 효율이 좋다.

3) deque 클래스 사용 : collections모듈의 deque는 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조. deque은 양방향이기 때문에 append(), pop()과 더불어 appendleft(), popleft()메소드가 있어 각각 맨 앞에 데이터를 삽입하거나 맨 앞에서 제거할 수 있다. appendleft(), popleft()메소드는 각각 시간복잡도가 O(1)이기 때문에 리스트보다 더 효율적이다.

 

▶ 일반적으로는 양방향을 지원하고 효율이 좋은 deque를 이용하여 큐를 구현한다.

 

* 덱(Deque) : 일반 큐와 달리 앞과 뒤 모두에서 데이터의 삽입과 삭제가 일어남. 스택과 큐의 일반화된 경우라고 볼 수 있는데 연결 리스트로 구현되어 있어 삽입과 삭제가 O(1)안에 끝나 매우 빠르다.

 

# 큐
from collections import deque

# deque 생성
queue = deque()

# append
# 오른쪽에 데이터 추가
queue.append(3) # deque([3])
queue.append(5) # deque([3,5])
queue.append(7) # deque([3, 5, 7])

# appendleft
# 왼쪽에 데이터 추가
queue.appendleft(2) # deque([2, 3, 5, 7])
queue.appendleft(4) # deque([4, 2, 3, 5, 7])

# pop
# 오른쪽에서 데이터 삭제
queue.pop() # 7
queue.pop() # 5

# popleft
# 왼쪽에서 데이터 삭제
queue.popleft() # 4
queue.popleft() # 2

queue # deque([3])

 

 

*주의할 점

파이썬 list를 활용해 큐를 만들면서 아래와 같이 insert를 활용해 자료를 추가할 경우, 삽입할 때 list 내부에 있는 모든 원소를 한 칸씩 이동시켜야 하기 때문에 O(n)의 시간 복잡도를 가진다. 따라서 시간 초과가 발생할 수도 있다.

 

queue = []

queue.insert(0,1) # [1]
queue.insert(0,3) # [3, 1]
queue.insert(0,5) # [5, 3, 1]

 

 

[힙(Heap)]

▶ 힙은 최댓값과 최솟값을 빠르게 찾아내기 위한 자료구조

▶ 우선순위 큐를 구현하기 위한 자료형으로 많이 쌓인다.

▶ 기본적으로 배열로 힙을 구현할 수 있지만, 한 번 정도만 본인 스스로 구현해보고 그냥 파이썬 heapq모듈 사용 추천

▶ 완전 이진 트리(Complete Binary Tree)로, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나 작아야 한다. 힙은 우선순위 큐를 구현하거나 힙 정렬을 하는 데 사용된다. 각 노드의 키 값이 그 자식의 키 값보다 작지 않거나(최대힙), 크지 않은(최소 힙)

* 완전이진트리는 중복을 허용하지 않지만 힙은 허용한다.

* <힙에서의 부모 자식 관계>

- 오른쪽 자식의 인덱스 = 부모의 인덱스*2 +1

- 왼쪽 자식의 인덱스 = 부모의 인덱스 *2

- 부모의 인덱스 = 자식의 인덱스/2

* 힙 사용 이유 : 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 O(n) vs 힙 : O(logn)

 

* 데이터 삽입 : 힙은 완전 이진 트리이기 때문에, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다.

 

*힙 정리

https://velog.io/@jsbryan/%ED%9E%99-%EC%B5%9C%EC%86%8C-%ED%9E%99-%EC%B5%9C%EB%8C%80-%ED%9E%99

힙 (최소 힙, 최대 힙)

 

 

*힙 모듈 사용법

https://buyandpray.tistory.com/30

[Python] heapq 모듈 사용법

 

 

 

[우선순위 큐]

▶ 큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다.

 

▶ 우선순위 큐는 데이터를 추가(put)한 순서와 상관없이 데이터를 꺼낼 때(Get)값을 오름차순하여 반환하는 특징을 갖고 있는 자료구조이다.

 

▶ 우선순위 큐는 힙(heap) 자료구조를 통해 구현할 수 있다. → put(), get()메서드는 O(log n)의 시간 복잡도를 가진다.

 

▶ 우선순위 큐는 최소한 두 가지 연산이 지원되어야 한다.

1) 하나의 원소를 우선순위를 지정하여 추가하는 함수(push)

2) 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 반환하는 함수(pop)