[자료구조/python] stack, queue

 

위 책을 토대로 궁금한 점을 추가 리서치 후 기술하였다.

---

스택

 

LIFO (Last In, First Out)

 

기존의 리스트 자료구조와 같지 않나 생각이 들었다. 하지만, python에서는 대체로 collections.deque 라이브러리를 이용해 구현했다. 그 이유가 궁금했다.

 

Q. 리스트 vs 배열

- 리스트: 적은 요소

- 배열: 매우 큰 요소를 저장하거나 수학적 연산이 필요할 경우 

	arr (배열)	list (리스트)
선언 필요성	O	X
값 정의	array.module, numpy	대괄호로 감싸주기만 하면 됨
사칙연산	쉬움	어려움
데이터 크기 (자료형?)	같아야함	X, 리스트 중첩 가능

 

 

Q. 리스트 vs 덱

- deque (덱): Double Ended Queue

	deque (덱)	list (리스트)
	양방향에서 삽입과 삭제가 일어나는 자료구조	random access에 최적화된 자료구조
데이터 삽입 / 삭제 (자료 양끝 한정)	O(1)	O(N) 지우고 나서, 한칸씩 앞으로 당겨주는 연산
인덱싱	O(N)	O(1) 고정된 사이즈의 메모리를 가지므로
슬라이싱	X	O
기타	maxlen 설정으로 오히려 메모리 오버 사용될 될 수도 있음	만약 stack 용도로 쓴다면 당겨주는 연산이 불필요해서 deque 보다 빠름

 

 

collections.deque 를 이용해 심플하게 예외 처리하기

[python deque 문서] / [백준 문제]

 

실습코드

Study-Algorithm/data_structure/fixed_stack.py at main · ddubbu-dev/Study-Algorithm

 

그 외 꿀팁

- stack; top >= bottom 등 pop, push 할 때 규칙; 말로 혹은 그림으로 정리해봐도 좋을 듯

- 고민; 언제 stack 구조를 써야할까?

- 세로로 쌓고 빼는 그림이 이해하기 쉬움

 

 

큐

 

FIFO (Firt In, First Out); 은행창구 대기, 스프링글스 통, 뱀의 움직임

 

- (dequeue) < front < (enqueue) < rear; 가로로 쌓고 빼는 그림이 이해하기 쉬움

- 배열, 링버퍼 (나머지 연산자 % 사용 주의) 등으로 구현 가능하지만, deque 모듈 권장

- stack과 사용법은 동일하되, append, popleft 메소드를 사용해서 단방향으로 추가 및 제거

 

 

Q. collections.deque vs queue.Queue 모듈 차이점?

- collections.deque : 단일 쓰레드 환경

- queue.Queue

Study-Algorithm/data_structure/fixed_queue.py at main · ddubbu-dev/Study-Algorithm

 

 

우선순위 큐

참고자료

 

우선 3가지 자료구조가 자칫 비슷해보일 수 있을 것 같아 차이점을 명시해보았다.

자료구조	삭제되는 요소
스택(Stack)	가장 최근에 들어온 데이터
큐 (Queue)	가장 먼저 들어온 데이터
우선순위큐 (Priority Queue)	가장 우선순위가 높은 데이터

 

 

- 우선순위와 함께 인큐 / 디큐할 때 우선순위가 높은 데이터를 꺼내는 방식

- 구현 시 heapq 모듈 사용; hea은 완전이진트리 구조이므로 삽입&삭제 연산을 위해 h=log(n+1) 시간만 들이면 된다.

- priority queue (thread-safe) vs heapq(non-safe); thread-safe 검증을 위해 시간이 더 걸리므로

 

 

그럼 heap은 무엇인가?

- 최댓값, 최솟값을 찾아내는 연산을 빠르게 하기위해 고안된 자료구조

- 완전이진트리이면서 (최대힙) key(root) ≥ key(child), (최소힙) key(root) ≤ key(child)

- 작동 원리 실습, 우선은 heapq 이용하기

 

위 특성을 응용해 우선순위큐를 구현할 수 있다.

 

[실습코드 in 백준]

https://www.acmicpc.net/source/82681827