Python | 자료구조 deque 데크 정의, stack queue 함수

deque 함수

• 정의 : 앞 뒤에서 데이터를 처리할 수 있는 양방향 자료형

• 문법

from collection import deque
a = [1, 2, 3, 4, 5]
q = deque(a)
q.rotate(2)  #시계방향 회전은 양수, 그 반대는 음수
list(q)

# output
[4, 5, 1, 2, 3]

# deque(a)로 deque 객체를 만든 후 rotate() 함수를 사용하여 
2만큼 오른쪽으로 회전하면 첫 값이 4를 가리키게 된다. 
마찬가지로 왼쪽으로 2만큼 회전하여 3을 가리키려면 2 대신 -2를 입력하면 된다.

• 기본연산

dq=deque() # 덱 생성
dq.append() # 덱의 가장 오른쪽에 원소 삽입
dq.popleft() # 가장 왼쪽 원소 반환
dq.appendleft() # 덱의 가장 왼쪽에 원소 삽입
dp.pop() # 가장 오른쪽 원소 반환
dp.clear() # 모든 원소 제거
dp.copy() # 덱 복사
dp.count(x) #x와 같은 원소의 개수를 계산

• 예시

>>> from collections import deque
>>> d = deque([1,2,3,4,5])
>>> d.append(6)
>>> d
deque([1, 2, 3, 4, 5, 6])
>>> d.appendleft(0)
>>> d
deque([0, 1, 2, 3, 4, 5, 6])
>>> d.pop()
6
>>> d
deque([0, 1, 2, 3, 4, 5])
>>> d.popleft()
0
>>> d
deque([1, 2, 3, 4, 5])
>>>

• 특징
  -deque는 list보다 속도가 빠르다. pop(0)와 같은 메서드를 수행할 때 리스트라면 O(N) 연산을 수행하지만, deque는 O(1) 연산을 수행하기 때문이다.

출처

.
.
✏️ stack과 queue 처럼 쓸 수 있다. 그럼 이 함수들에 대해서 알아보자
.
.

stack 함수

• 정의 : 가장 나중에 들어온 자료가 가장 먼저 처리되는 LIFO(last in first out) 자료구조

• 기본연산

from pythonds.basic.stack import Stack

- push() : 스택에 원소를 추가한다.
- pop() : 스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.
- peek() : 스택 가장 위에 있는 원소를 반환한다. (삭제하지는 않는다.)
- empty()/isEmpty() : 스택이 비어있다면 1, 아니면 0을 반환한다.
- size() : 스택에 요소가 몇 개 들어있는지 출력해주는 연산
- items() : 스택에 어떤 요소가 있는지 리스트 형태로 출력하는 연산

출처 / 출처2 / 출처3
.
.

queue 함수

• 정의 : 가장 처음 들어온 자료가 가장 먼저 처리되는 FIFO(fist in first out) 자료구조

• 기본 연산

-put(x) : 데이터 추가 시
-get(x) : 데이터 삭제 시

>>> from queue import Queue
>>> que = Queue()
>>> que.put(1)
>>> que.put(2)
>>> que.put(3)
>>> que.get()
1
>>> que.get()
2