[자료구조] 스택 , 큐, 데크 파이썬

자료구조

사전적의미로는 데이터를 체계적으로 저장하고 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리를 의미합니다.

자료 구조의 종류로는 스택, 큐, 그래프, 트리 등 다양한 구조가 있지만 이중에서 스택과 큐에대해 설명하겠습니다.

 

스택 큐 핵심

데이터를 삽입 하고 삭제하는 기능이 핵심 기능입니다. 

자료 구조에 더이상 삽입할 수 없으면  오버플로우 삭제 할 수 없으면 언더플로우가 발생합니다.

 

스택

선입후출(First In Last Out) 이라는 먼저 들어온 데이터가 가장 마지막으로 꺼낼 수 있는 구조입니다.

스택은 프링글스 통을 생각하면 스택에 구조 이해에 쉽습니다. 왜냐하면 프링글스 통에서 맨 아래의 과자를 꺼낸다고 생각할 때  포장과정에서는 가장 먼저 들어가지만 우리가 먹기 위해서는 가장 마지막으로 꺼내기 때문입니다.

stack = []

stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
print("스택  : ", stack)
data = stack.pop()
print("스택 " ,stack)
print("스택에서 꺼낸 값 " ,data)

 

스택

파이썬에서 스택을 구현할 때 리스트로도 간단하게 구현할 수 있습니다.

append 함수를 통해 데이터를 삽입하고 pop 을 통해 데이터를 꺼내고 삭제 할 수 있습니다.

위 코드에서 알 수 있듯이 가장 나중에 들어오는 데이터를 꺼내는 것을 확인할 수 있습니다.

 

큐

선입선출(First In First Out) 이라는 먼저 들어온 데이터가 가장 먼저 꺼낼 수 있는 구조입니다.

큐는 줄을 설 때 구조라고 생각하면 이해하기 쉽습니다. 

예를 들어 놀이공원에 가서 줄을 서야할 때 먼저 줄 선 사람이 먼저 놀이기구를 타는 구조를 생각하면 됩니다.

from collections import deque
queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

print("큐 구조 : ", queue)
data = queue.popleft()
print("큐 구조 : ",queue)
print("큐에서 꺼낸 값 ",data)

 

큐

파이썬에서 큐를 사용하기 위해서는 collections 에 있는 deque를 이용해 구현할 수 있습니다.

append 함수를 이용해 데이터를 삽입할 수 있고 popleft 함수를 통해 먼저 들어온 데이터를 꺼낼 수 있습니다.

 

deque 란?

deque란 양 쪽 끝에서 데이터를 삽입 삭제할 수 있는 구조로 스택과 큐의 기능을 모두 사용할 수 있는 자료 구조입니다.

위에서는 큐 기능을 구현하기 위해서 popleft 함수를 사용했습니다. 하지만 리스트로 만들었을 때 값을 꺼냈던 기능 pop() 함수도 똑같이 이용할 수 있습니다.

 

deque 쓰는 이유

스택 기능을 구현해야할 때 굳이 list 로 구현해도 되는데 deque 로 구현하는 코드가 있습니다. 굳이 똑같은 기능을 하는데 deque 로 만들어서 알고리즘 문제를 해결하는 이유가 뭘까요?

이유는 성능과 기능입니다. 

list 로 구현할 경우 O(n) 의 시간이 걸리지만 deque 로 구현하면 O(1) 의 속도로 성능을 향상시킬 수 있기 때문입니다.

또한 list는 스택 기능만 사용할 수 있지만 deque 는 큐 기능도 사용할 수 있기 때문입니다.

그리고 deque를 리스트로 변환하고 싶을 때 list(데크) 로 간편하게 파이썬에서 변환할 수 있습니다.