자료구조 - 스택, 큐, 우선순위 큐 (2)

 

예? 이걸 몰라요?

 

스택, 큐, 우선순위 큐

3가지의 자료구조는 전공자라면 알고있는 개념이다.

 

알고리즘을 본격적으로 학습하기 위해서 필수적으로 알고있어야 하는 자료구조인데,

코테에서도 필수적으로 익혀두고 있어야 하는 자료구조이다.

 

크게 어렵지 않은 개념이기 때문에 빠르게 습득할 수 있을 것이다!

 

 

---

 

0. 앞서서,

 

나는 파이썬으로 코테를 준비하고 있으니, 파이썬을 기준으로 해서 자료구조를 설명하겠다!!

 

스택과 큐는 리스트에서 조금 더 발전한 형태의 자료구조이다.

두 개는 비슷한 구조를 갖고 있지만, 처리 방식은 다르다는 것을 알고가자

 

---

1. 스택

 

스택은 "삽입"과 "삭제" 연산이 후입선출(LIFO:Last In First Out)로 이뤄지는 자료구조이다.

후입선출 - 말 그대로 나중에 들어간게 먼저 나옴

스택

 

그림을 보자!

 

우리는 새 값을 넣을 수 있고(push), 가장 최근의 값을 제거할 수 있다(pop) - 후입선출(LIFO)

새 값이 스택에 들어가게 되면 top이 새 값을 가리킨다. top은 스택의 맨 위 값을 가리킨다.

 

파이썬에서는 리스트를 활용하여 아래처럼 스택을 구현할 수 있다!

 

 

조건

top : 삽입과 삭제가 일어나는 위치 (스택에서 가장 꼭대기)

s = [] (s는 리스트) --> 파이썬에서 스택을 구현하기 위해서는 그냥 리스트만 선언해주면 됨!

 

명령어

	명령어	역할
삽입	s.append(data)	top위치에 data를 추가한다 (단순 추가만!!!)
제거	s.pop()	top위치에 있는 데이터를 삭제하고 확인도 할 수 있다 (삭제하고 확인도 가능!!!)
확인	s[-1]	top위치에 있는 데이터를 확인할 수 있다 (확인만!!!)

 

쉽져?

 

스택은 깊이 우선 탐색(DFS : Depth First Search), 백트래킹 같은 알고리즘 ==> 코테에 많이 사용되고 효과적이니깐,

반드시 알아두도록 하자!

후입선출 개념자체는 재귀 함수 알고리즘 원리와 통한다는 것도 알아두자!

 

---

 

2. 큐

 

큐는 삽입과 삭제 연산이 선입선출(FIFO : First In First Out)로 이뤄지는 자료구조 이다.

선입선출 말그대로, 먼저 들어온 데이터가 먼저 나오는 구조이다.

먼저 들어온 것이 먼저나가는 구조이니, 삽입과 삭제는 양방향에서 이루어진다는 것을 알 수 있다!

 

큐

 

그림을 보면, 새로운 데이터는 Rear(뒤) 부분에 추가되고,

Front(앞) 에서 데이터의 삭제가 이루어진다.

 

일반적으로 큐에서, 데이터가 추가되는 과정을 "Enqueue",

데이터가 삭제되는 과정을 "Dequeue"라고 부른다.

 

파이썬에서는 deque라이브러리를 사용해서 큐를 구현한다!

 

 

조건

rear : 큐에서 가장 끝의 데이터를 가리키는 영역!

front : 큐에서 가장 앞의 데이터를 가리키는 영역

 

그리고 아래와 같이 라이브러리를 import 해주고,

큐를 선언해야 한다는 것을 알아두자!

# 큐를 사용하기 위한 라이브러리 import
from collections import deque

# 큐를 선언
myQueue = deque()

 

 

명령어

 

	명령어	역할
삽입	myQueue.append(data)	rear 부분에 데이터를 삽입한다 (맨 뒤에 데이터를 추가한다!!)
제거	myQueue.popleft()	front 부분의 데이터를 삭제하고 확인한다 (맨 앞의 데이터를 삭제하고 확인도 가능!!)
확인	myQueue[0]	front에 있는 데이터를 확인한다 (맨 앞의 데이터를 확인만!!)

 

이것도 쉽져? 스택과 동일하게 리스트 기반의 구조를 갖고 있지만,

처리방식이 다르다는 것을 알 수 있습니다!!

 

큐는 너비 우선 탐색 (BFS : Breadth First Search)에서 자주 사용한다!

이것도 스택과 함께 잘 알아두도록 하자!

---

 

3. 우선순위 큐

우선순위 큐 (priority queue)는,

값이 들어간 순서와 상관 없이

우선순위가 높은 데이터가 먼저 나오는 자료구조이다!

 

말 그대로, 우선순위가 있는 자료구조 이므로,

우선순위 기준으로 내부적으로 정렬이 이루어지는 큐라고 볼 수 있다!

 

"우선순위 큐"도 큐의 종류 중 하나이니, 큐의 성질을 갖고 있는데

우선순위 큐는, 큐 설정에 따라 front에 최대값 또는 최소값이 위치할 수 있다!

 

우선순위 큐는 일반적으로 힙을 이용하여 구현하는데 (힙은 트리 종류 중 하나)

그래서 이건 나중에 알아보도록 하자!

 

정리하자면,

"기본적으로 우선순위 큐는, 제거될 때 가장 작은 값을 제거함.

즉, 내부적으로 데이터를 정렬된 상태로 보관하는 매커니즘이 존재!!

데이터 정렬은, heapq 모듈을 통해 구현되어 있음"

 

만약 단순 오름차순이 아닌 다른 기준으로 원소가 정렬되기를 원한다면, 

(우선순위, 값)의 튜플의 형태로 데이터를 추가하고 제거하면 된다!! (아래 코드에서 설명)

 

 

우선순위 큐

 

위 그림은 최소값을 기준으로 정렬된 우선순위 큐이다.

 

최소값(높은 우선순위)은 맨 앞에 위치하며 -> 먼저 삭제되는 우선순위를 가짐

최대값(낮은 우선순위)이 맨 뒤에 추가된다.

 

파이썬의 우선순위 큐 라이브러리를 사용하면 데이터들이 추가될때마다,

정렬된다는 것을 알아두자!! (내가 설정해둔 정렬 기준에 따라)

 

이번에는 명령어를 표로 정리하는 것 보다는 코드로 보여주는 것이 나을 거 같아서 예시코드를 첨부해봤습니다!

우선순위 큐를 선언해서 사용하기는 쉬운데, 정렬기준을 새로 설정하여 우선순위 큐를 사용하는 방법도 반드시 알아두자!!

# 우선순위 큐 라이브러리 사용
from queue import PriorityQueue

# 우선순위 큐 선언
q = PriorityQueue()
que = PriorityQueue()
que1 = PriorityQueue()


# 우선순위 큐 명령어들

q1 = PriorityQueue(maxsize=10) # maxsize를 활용하면 크기 제한 가능

# 우선순위 큐에 원소 추가
que.put(4)
que.put(1)
que.put(7)
que.put(3)

# 우선순위 큐 원소 삭제!
print(que.get())  # 1
print(que.get())  # 3
print(que.get())  # 4
print(que.get())  # 7

# 정렬 기준 변경 가능!!! (우선순위, 값)의 튜플 형태로 정렬 기준 설정 가능
que.put((3, 'Apple'))
que.put((1, 'Banana'))
que.put((2, 'Cherry'))

print(que.get()[1])  # Banana
print(que.get()[1])  # Cherry
print(que.get()[1])  # Apple



# 절댓값을 기준으로 정렬하고 같으면 음수 우선 정렬하도록 구성 가능!!
req1 = 3
req2 = -3

# 3, -3을 저장할때 절댓값 기준이면 두 수의 우선순위는 동일
# 하지만, req1, req2를 비교했을 때 -3이 더 작기 때문에 우선순위가 높음(기본 우선순위 큐에서는 작은 값이 우선순위가 높다)
que1.put((abs(req1),req1)) # 3을 저장
que1.put((abs(req2),req2)) # -3을 저장

# 그래서 -3, 3 순으로 출력!!
print(que1.get()[1]) # -3
print(que1.get()[1]) # 3

 

 

참고로, 내부적으로 heap 모듈을 사용하는 PriorityQueue 클래스의 put(), get() 함수는 O(log n)의 시간 복잡도를 가진다!!