stack(스택)
입구가 한쪽 밖에 없는 자료구조 LIFO(Last In First Out)
push와 pop을 활용하여 조작하며 가장 최상위 스택을 가르키는 top 포인터로 구성된다.
파이썬에서의 연산
.append() 함수와 .pop() 함수를 섞어서 구현한다.
queue(큐)
입구와 출구가 따로 있는 자료구조 FIFO(First In First Out)
enQueue와 deQueue로 조작하며 첫번째 원소를 가르키는 front 마지막 원소를 가르키는 rear로 구성된다.
원형 큐
단순 큐의 경우 원소가 삭제되어 메모리가 비더라도 재활용하지 못하는 단점이 있는데 이를 보완하기 위해 큐의 양끝을 연결한 것이 원형 큐 이다.
파이썬에서의 연산
collections 라이브러리의 deque 메소드를 활용한다.
.append() 함수와 .popleft() 함수를 섞어서 구현한다.
deque(데크)
queue 두개를 이어서 붙인 구조로 양끝에서 삽입과 삭제연산이 가능하다.
파이썬에서의 이용 collections 모듈
from collections import deque
백준 2164번에서의 사용예시 처음 del은 O(n)의 복잡도를 가졌으나 leftpop 함수로 0(1)로 개선할 수 있었다.
메소드
append(x) - 데크의 오른쪽에 x를 추가한다.
appendleft(x) - 데크의 왼쪽에 x를 추가한다.
clear() - 데크에서 모든 요소를 제거하고 길이가 0인 상태로 만든다.
copy() - 데크의 얕은 복사본을 만든다.
count(x) - x와 같은 데크 요소의 수를 센다.
extend(iterable) - iterable 인자에서 온 요소를 추가하여 데크의 오른쪽을 확장한다.
extendleft(iterable) - iterable에서 온 요소를 추가하여 데크의 왼쪽을 확장한다. 일련의 왼쪽 추가는 iterable 인자에 있는 요소의 순서를 뒤집는 결과를 준다.
index(x,[start, stop]) - 데크에 있는 x의 위치를 반환한다.(start 이후 stop 이전) 첫 번째 일치를 반환하거나 찾을 수 없으면 ValueError를 발생시킨다.
insert(i,x) - x를 데크의 i위치에 삽입한다. 삽입으로 인해 제한된 길이의 데크가 maxlen 이상으로 커지면 indexError가 발생한다.
pop() - 데크의 오른쪽에서 요소를 제거하고 반환한다. 요소가 없으면 indexError를 발생시킨다.
popleft() - 데크의 왼쪽에서 요소를 제거하고 반환한다. 요소가 없으면, indexError를 발생시킨다.
remove(value) - value의 첫 번재 항목을 제거한다. 찾을 수 없으면 valueError를 발생시킨다.
reverse() - 데크의 요소들을 제자리에서 순서를뒤집고 None을 반환한다.
rotate(n=1) - 데크를 n단계 오른쪽으로 회전한다. n이 음수이면, 왼쪽으로 회전한다. 데크가 비어 있지 않으면, 오른쪽으로 한 단계 회전하는 것은 d.appendleft(d.pop())와 동등하고, 왼쪽으로 한 단계 회전하는 것은 d.append(d.popleft())와 동등하다.
maxlen - 데크의 최대 크기 또는 제한이 없으면 None
참고자료
https://medium.com/@rasmussen.matias/fun-with-deques-in-python-31942bcb6321
https://docs.python.org/ko/3/library/collections.html?highlight=deque#collections.deque
백준 2164번 카드2
