Linear Data Structure: 스택, 큐, 덱

 

개념

자료 간의 연결 형태에 따라 자료구조의 종류를 구별했을 때, 자료를 순차적으로 나열한 형태를 선형 자료구조라고 한다. 하나의 자료 뒤에 다른 하나의 자료가 오는 형식으로 선형 자료구조 안에서도 기본, 제한으로 나뉜다. 이 글에서는 제한 선형 자료구조에 속하는 스택, 큐, 덱에 대해 정리한다.

 

 

스택(Stack)

 

출처 : https://ko.wikipedia.org/

 

스택, 큐, 덱의 가장 큰 차이점은 데이터의 출입 방향이다. 스택은 데이터가 들어오고 나가는 길이 한 방향 밖에 없어서 데이터를 스택에서 뺄 경우 위의 사진과 같이 들어온 곳으로 나가게 된다. 책을 쌓는 것처럼 아래쪽부터 값이 차곡차곡 쌓이기 때문에 나중에 들어온 데이터가 먼저 나가는 LIFO(Last In First Out, 후입선출) 구조이다. 위 이미지처럼 세로 형태로 스택을 설명하는 그림이 굉장히 많은데, 배열로 스택을 구현하게 되면 가로 형태로 표현하는 배열과 위 이미지가 조금 헷갈릴 수 있다. (는 사실 내가 헷갈렸기 때문에 😅)

 

결론부터 말하면 배열에서는 인덱스가 클수록 나중에 들어온 원소가 된다.

 

stack = []

stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

print("- - - - - 데이터 삽입(push) - - - - -")
print(stack)
print("\n")

print("- - - - - 데이터 삭제(pop) - - - - -\n")
while len(stack) != 0:
    v = stack.pop()
    print(v)

 

개념만 구현해본 위 코드의 실행 결과는

 

💡 queue 모듈(import queue)의 LifoQueue()를 이용해서 스택을 구현하는 방법도 있다.

 

 

큐(Queue)

 

큐는 입구와 출구가 다르다. 큐의 맨 끝인 Back(또는 Rear)으로 Enqueue라는 데이터 입력 함수를 통해 데이터를 추가하고 Front에서 Dequeue라는 데이터 삭제 함수를 통해 데이터를 제거한다. 스택과 다른 점은 들어온 순서대로 데이터가 나가기 때문에 FIFO(First In First Out, 선입선출) 구조라는 것이다. 파이썬에서는 collections 모듈에 내장된 deque나 queue(사용법은 스택과 동일)의 Queue()를 이용해서 큐를 구현할 수도 있다. 

 

from collections import deque

queue = []

# deque 사용 X

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

print("- - - - - 데이터 삽입(enqueue) - - - - -")
print(queue)
print("\n")

print("- - - - - 데이터 삭제(dequeue) - - - - -")
while len(queue) != 0:
    # 0번 인덱스를 pop
    v = queue.pop(0)
    print(v)

print()

# deque 사용
usingDeque = deque([1, 2, 3, 4, 5])

print("- - - - - 데이터 삭제(dequeue) - - - - -")
while len(usingDeque) != 0:
    v = usingDeque.popleft()
    print(v)

 

스택과 동일하게 개념만 간단하게 구현한 코드의 실행 결과는

 

💡 위에서 설명한 큐는 가장 기본적인 선형 큐인데 선형 큐의 단점을 보완하기 위한 원형 큐(Circular Queue)나 데이터가 정렬된 상태일 때 사용하는 우선순위 큐(Priority Queue)도 존재한다.

 

 

덱(Double-ended queue, Deque)

출처 : https://www.programiz.com/dsa/deque

 

데이터 삽입/삭제가 앞뒤에서 다 가능하다. 스택과 큐를 합쳐놓은 형태로 스택처럼 쓸 수도 있고 큐처럼 쓸 수도 있다. 데이터 삽입/삭제 시 시간 복잡도가 O(1)이기 때문에 연산 속도가 빠르다. 크기가 가변적이기 때문에 저장할 데이터 개수를 모를 때에도 사용할 수 있다는 장점도 있다. collections 모듈의 deque 객체를 이용해 구현할 수 있고 사용할 수 있는 메서드는 아래와 같다.

 

 

각각의 메서드에 대한 자세한 설명은 여기에 잘 나와있다.