스택, 큐, 덱 파이썬으로 구현

스택

후입선출(Last In First Out) 구조이다.

삽입과 삭제하는 방향이 동일하다

 

파이썬에서 스택은 리스트를 활용한다.

append()는 가장 뒤에 데이터를 삽입하고, pop()은 가장 뒤의 데이터를 꺼낸다.

 

stack = []

# 삽입(1) - 삽입(2) - 삽입(3) - 삭제(3)
stack.append(1)
stack.append(2)
stack.append(3) #뒤쪽에 원소 삽입하기

stack.pop() # 맨 위(맨 뒤)의 원소 꺼내기

print(stack[len(stack)-1] # 맨 위의 원소 출력하기 peek()

 

 

큐

선입선출(First In First Out) 구조이다.

삽입과 삭제하는 방향이 다르다.

스택과 달리 공정한 자료구조이다.

 

큐는 구현을 위해 덱 라이브러리를 사용한다.

먼저 들어온 원소, 즉 맨 왼쪽의 원소부터 삭제하므로 popleft()를 사용한다. 

from collections import deque

queue = duque()

# 삽입(1) - 삽입(2) - 삭제(1)
queue.append(1)
queue.apppend(2)

queue.popleft()

 

 

덱 

스택, 큐와 달리 모든 방향에서 삽입과 삭제가 가능하다

왼쪽 삽입은 appendleft(), 오른쪽 삽입은 append()를 사용한다.

왼쪽 삭제는 popleft(), 오른쪽 삭제는 pop()을 사용한다.

 

from collections import dequeue

deq = dequeue()

deq.appendleft(1)  # ([1])
deq.appendleft(2)  # ([2, 1])
deq.append(3)      # ([2, 1, 3])
deq.popleft()      # ([1, 3])
deq.appendleft(4)  # ([4, 1, 3])
deq.pop()          # ([4, 1])