4-1. 스택
스택stack
- 데이터를 임시 저장할때 사용하는 자료구조, 후입선출(LIFO)
- 데이터 넣는 작업을 푸시push, 꺼내는 작업을 팝 pop
- 리스트로 구현, 크기capacity는 len(stk)
- 쌓여있는 데이터 개수: 스택 포인터, 비어있으면 0, 가득차면 =스택 크기
4-2. 큐
큐 queue
- 선입선출 구조(FIFO)
- 데이터 추가: 인큐, 데이터 꺼냄: 디큐
- 데이터 꺼내는 쪽: 프런트, 데이터 넣는 쪽: 리어
- 배열로 구현, 덱(deque) 사용하면 빠름
- 우선순위 큐
- 인큐할때는 우선순위 부여하여 추가
- 디큐할 때는 우선순위 높은 데이터 꺼내는 방식
- heapq모듈 사용
- heapq.heappush(heap, data) : 인큐
- heap.heappop(heap) : 디큐
- 디큐해도 원소 옮기지 않는 큐 - 링 버퍼
- 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조
- front, rear를 변경하여 원소 옮기지 않고 업데이트
- 인큐할때 rear += 1, rear == capacity 면 rear = 0 으로 바꿈
- 디큐할때front += 1, front == capacity 면 front = 0 으로 바꿈
- 오래된 데이터 버리는 용도로 활용
- 인덱스 count(0 ++) % n(저장할 개수)으로 구현
덱(deque)
from collections import deque로 라이브러리 불러와서 사용- 스택, 큐 구현가능
- deque 덱: 맨 앞과 맨 끝 양쪽에서 원소를 추가, 삭제할 수 있는 자료구조
.popleft(), .appendleft(), .extendleft()사용하면 리스트 맨 앞에 원소 추가, 삭제- 양 끝에 접근할때는 시간복잡도 O(1)이지만, 중간은 O(n)
나의 개발기록