[자료구조] 스택(stack), 큐(queue), 덱(dequeue)

1. Stack

스택(Stack)은 컴퓨터의 가장 기본적인 자료구조 중 하나이다. 후입선출(Last in, First Out, LIFO)의 형태를 가지고 있는 자료구조로 가장 마지막에 입력된 데이터가 가장 먼저 제거되는 구조이다. insert()를 통해서 원하는 위치에 데이터를 넣을수도 있지만 보통 append()를 사용하여 마지막에 데이터를 추가한다. 그리고 꺼낼 때에는 pop()을 사용하여 마지막 데이터를 꺼낸다.

https://wikidocs.net/198491

2. Queue

스택과 반대로 선입선출(First in, First Out) 형태의 자료구조가 큐이다. 큐에 데이터를 넣을 때는 스택과 마찬가지로 마지막에 데이터를 추가하지만, 데이터를 꺼낼 때에는 가장 앞에 있는 것을 먼저 꺼낸다.

https://wikidocs.net/198491

3. Dequeue

파이썬에서는 덱(Deque)이라는 것을 많이 사용한다. 파이썬 내장 모듈인 collections에 있는 것으로 스택 + 큐인 자료구조라고 생각하면 된다. 덱은 Double Ended QUEue의 약자이다. 리스트에 가장 앞에 있는 데이터를 꺼내기 위해서는 pop(0)을 사용했지만, deque에서는 popleft() 함수를 사용한다. 이 함수를 사용해도 pop(0)처럼 비효율적(-> 꺼내고 뒤에 있는 값들을 다 하나씩 이동하는 시간복잡도 O(N)을 가짐)이지 않고 O(1)의 시간복잡도를 가진다.

deque는 앞 뒤로 데이터를 넣을수도 있다. 앞에서 데이터를 넣을 때에는 appendleft() 함수를 사용한다. deque의 간단한 사용방법과 함수를 코드로 알아보자,

3-1. Dequeue의 사용방법

from collections import deque

dq = deque() # 덱 생성

dq.append(1) # dq에 뒤로 데이터 넣기
dq.appendleft(2) # dq에 앞으로 데이터 넣기

print(dp.pop()) # 1, 맨 뒤의 데이터 꺼내기
print(dp.popleft()) # 2, 맨 앞의 데이터 꺼내기

3-2. Dequeue의 함수

함수	설명
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()	데크의 요소들을 제자리에서 순서를 뒤집는다
rotate(n)	데크를 n단계 오른쪽으로 회전한다 n이 음수이면, 왼쪽으로 회전한다