2.2 큐 & 스택 (Queue & Stack)

큐(Queue)

💡 Queue

queue는 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조입니다.

queue의 rear(뒤)에 데이터를 추가하는 것을 enqueue라고 합니다. 또한 queue의 front(앞)에서 데이터를 꺼내는 것을 dequeue라고 합니다.

 

FIFO (First In First Out)

List 기반 queue 구현

python에서 queue를 가장 간단히 구현하는 방법은 단순하게 list를 이용하는 것입니다. list의 append 메서드를 사용하면 맨 뒤에 데이터가 추가 되고, pop을 하게 되면, 맨 앞의 데이터가 나오기 때문입니다. 여기서 주목해야 할 점은 list로 queue를 구현하면 dequeue 연산의 시간복잡도가 O(n)이 된다는 점입니다.

# queue 선언
q = []

# enqueue O(1)
q.append(1) # [1]
q.append(2) # [1, 2]
q.append(3) # [1, 2, 3]

# dequeue O(n)
q.pop(0) # [2, 3]
q.pop(0) # [3]

# front 확인하기
q[0]

# rear 확인하기
q[-1] == q[len(q)-1]

Linked list 기반 queue 구현 - deque 활용하기

list를 이용하면 dequeue 연산의 시간복잡도가 $O(n)$이 되기 때문에, 우리는 doubly linked list를 이용해서 queue를 구현할 겁니다. doubly linked list를 이용하면 enqueue, dequeue 모두 $O(1)$으로 실행할 수 있습니다.

doubly linked list를 이용해서 queue를 구현한다고 했는데, 직접 doubly linked list를 구현할 필요는 없습니다. 왜냐하면 collections 라이브러리의 deque이 doubly linked list로 구현되어 있기 때문입니다. 그래서 우리는 queue를 구현하기 위해 deque을 사용할 겁니다.

⁽¹⁾ deque 은 double-ended queue의 약자로, 내부 구조가 doubly linked list로 구현되어 있어, 맨 앞, 맨 뒤 모두 데이터의 삽입과 제거가 가능한 자료구조입니다.

 

Doubly linked list로 구현되어 있기에 모든 연산이 O(1)의 시간 복잡도를 갖습니다. 그래서 deque를 활용하는 것이 O(n)의 시간복잡도를 가지는 list 기반으로 구현할 때보다 효율적이라 할 수 있습니다. 시간 복잡도를 다시 정리해 보자면 다음과 같습니다.

from collections import deque

# deque 선언
q = deque()

# enqueue O(1)
q.append(1) # [1]
q.append(2) # [1, 2]
q.append(3) # [1, 2, 3]
q.appendleft(0) # [0, 1, 2, 3]

# dequeue O(1)
q.popleft() # [1, 2, 3]
q.popleft() # [2, 3]
q.pop() # [3]

비어있는 Queue 검사 (deque)

• Queue - 빈 queue 검사하기⁽²⁾

dequeue를 통해 순차적으로 queue에 담긴 데이터에 접근할 때, 반복문 조건으로 deque을 그대로 사용할 수 있습니다. deque에 담긴 데이터가 존재한다면, 반복문을 실행하고, 그렇지 않다면, 반복문을 종료합니다. 다음 예시 코드를 보도록 하겠습니다.

q = deque([1, 2, 3, 4, 5])

while q:
		print("Dequeued element :", q.popleft())

print("End of queue")

• 결과
• Dequeued element : 5 Dequeued element : 4 Dequeued element : 3 Dequeued element : 2 Dequeued element : 1 End of queue

스택 (Stack)

💡 Stack

stack은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out) 형식으로 데이터를 저장하는 자료구조입니다.

stack의 top에 데이터를 추가하는 것을 push라고 하고 stack의 top에서 데이터를 추출하는 것은 pop이라고 합니다.

 

LIFO (Last In First Out)

 

 

List 기반 stack 구현

Stack에서도 deque를 사용해야 할까요? 그렇지 않습니다. queue 구현에 deque를 사용했던 이유는, doubly linked list의 구조를 활용해서 dequeue에 대한 시간복잡도를 줄이기 위한 것이었습니다.

Python에서 Stack은 list만으로 간단하게 구현할 수 있습니다. list의 top에서 push 메서드를 통해 데이터를 추가하고, pop 메서드를 이용해서 데이터를 삭제하는 것을 $O(1)$의 시간 복잡도로 수행할 수 있습니다.

# stack 선언
s = []

# push - O(1)
s.append(1) # [1]
s.append(2) # [1, 2]
s.append(3) # [1, 2, 3]

# pop - O(1)
s.pop() # [1, 2]
s.pop() # [1]

# top 확인하기
s[-1] == s[len(s)-1]

Stack - 빈 스택 검사

• Stack - 빈 stack 검사하기⁽³⁾

Stack을 이용하는 문제에서도 거의 반복문을 사용합니다. Queue에서 했던 방식과 동일한 형태로 사용하면 됩니다. stack에 데이터가 존재하면, 반복문을 돌리고, 반대로 비어있는 상태라면, 반복문을 더는 실행하지 않게 됩니다. 다음 예시 코드를 참고하시기를 바랍니다.

stack = [1, 2, 3, 4, 5]

while stack:
	print("Popped element :", stack.pop())

print("End of stack")

• 결과
• Popped element : 5 Popped element : 4 Popped element : 3 Popped element : 2 Popped element : 1 End of stack

Queue / Stack 사용시 주의사항

Queue - deque 인자 올바르게 활용하기

앞서 말씀드린 것처럼 python은 deque를 활용해서 queue를 구현합니다. 이때, deque의 인자의 자료형은 Iterable 객체로 제한됩니다.

<aside> 💡 Iterable 객체 : 반복문에서 반복될 수 있는 객체 ex) 리스트(list), 튜플(tuple), 집합(set), 딕셔너리(dictionary), 문자열(string) 등

</aside>

# list
a = deque([1, 2, 3, 4])   # deque([1, 2, 3, 4])

# tuple
b = (1, 9)
c = deque(b)              # deque([1, 9])

# set
b = {1, 3, 4}
c = deque(b)              # deque([1, 3, 4])

# dictionary
b = {'a':1, 'b':3, 'c':4}
c = deque(b)              # deque(['a', 'b', 'c'])

# string
b = "abcdefg"
c = deque(b)              # deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])

 

주의 사항 1) non-iterable한 객체를 직접 인자로 넣지 않기

# 원하는 결과 : deque([0])

a = deque(0)         # 올바르지 못한 사용 (TypeError : 'int' object is not iterable)

a = deque([0])       # 올바른 사용

 

 

주의 사항 2) Iterable 객체를 원소로 갖는 deque 만들기

: Iterable한 객체가 unzip 되어서 각각 하나의 요소로 들어갑니다.

# 원하는 결과 : deque([[1, 2]])

a = deque([1, 2])   # 올바르지 못한 사용 : 1, 2라는 int형 객체 2개로 이루어진 deque
                    # deque([1, 2])

a = deque()         # 올바른 사용 : [1, 2]를 하나의 원소로 가진 deque
a.append([1, 2])    # deque([[1, 2]])

Stack - Top을 통해서만 데이터 접근하기

위에서 설명했듯이, stack은 top에서 push 혹은 pop 을 통해 데이터 입력 및 추출이 가능한 자료구조입니다. top이 아닌 위치에 대한 접근은 지양해야 합니다. 오직 -1 index만 사용해서 stack의 top에 접근해야 합니다.

stack = [1, 2, 3, 4, 5]

stack[2] = 9            # stack에 대한 올바르지 못한 접근 : stack 중간 위치의 값 변경
												# 현재 stack = [1, 2, 9, 4, 5]

stack[-1]               # top에 있는 값에 접근 - 결과 : 5
stack[len(stack)-1]     # 또다른 top에 대한 접근 - 결과 : 5

Python에서 제공하는 list는 동적 메모리 할당이기 때문에, 데이터 추가에 대한 제한은 없습니다. 하지만, 데이터 제거를 하는 것에는 한계가 있습니다. 비어있는 stack에서 -1 index로 pop을 하는 것은 존재하지 않는 index를 이용한 접근이라 list index out of range라는 오류 메시지를 받게 됩니다.

stack = []

stack[-1]               # 오류 발생! : list index out of range
stack[len(stack)-1]     # 오류 발생! : list index out of range

 

 

코딩 테스트 활용

Queue - BFS 구현

그래프의 순회 방식 중 하나인 BFS 구현에서 queue는 현재 정점에 인접한 정점들을 저장하고, 순차적으로 front에서 dequeue해서 각 정점을 방문합니다. 자세한 설명은 그래프에서 진행될 예정입니다.

Queue - 투 포인터 사용

투 포인터(two pointer) 알고리즘은 두 포인트의 위치를 기록하는 것을 활용하는 알고리즘입니다. 해당 예시의 대표적인 문제로 2022 카카오 기술 인턴십의 ‘두 큐의 합 같게 만들기’가 있습니다. 한 큐에서 dequeue된 값은 다른 큐에 enqueue된다는 특성을 이용해서 2개의 queue를 1개의 queue로 이어서 투 포인터 알고리즘으로 2개의 큐로 나누는 지점을 찾아가는 방식으로 시간 복잡도를 줄일 수 있습니다.

Stack - 짝 맞추기

해당 유형의 문제는 새로운 값이 push하려할 때, 기존 stack의 top과 짝을 이루게 되면, push하려는 값과 기존 top을 같이 pop하는 방식입니다. 대표적인 예시로는 유효 괄호 쌍 검사, 동일 블록 제거하기, 등의 문제가 있습니다.

Stack - 되돌리기

가장 직관적으로 Stack을 생각할 수 있는 문제 유형입니다. stack에 임시로 데이터를 저장하다가 top에서 가장 최근에 push했던 값을 확인할 수 있습니다.

Stack - DFS(재귀)

DFS 알고리즘은 깊이 우선 탐색으로, 그래프 순회 알고리즘의 또 다른 방식입니다. 여기서 핵심은 재귀적 함수 호출인데, 이것이 Stack이 사용되는 예시입니다. 메모리적 관점으로 보면, 현재 수행 중인 함수에서 자기 자신을 다시 호출해서 또 다른 메모리 공간을 차지하게 됩니다. Stack으로 따지면, 재귀적 함수 호출은 append를, 함수 종료는 pop을 하는 것과 같은 형태를 가집니다. DFS와 재귀는 이후 내용에서 자세하게 다시 설명할 예정입니다.

def dfs(cur_v):
    visited[cur_v] = True
    for next_v in graph[cur_v]:
        if next_v not in visited:
            dfs(next_v)

visited = {}
graph = {...}
dfs(0)

 

 

Queue - deque을 사용해야하는 이유

list로 구현한 queue에서 O(1)의 시간복잡도로 Dequeue를 수행할 수 있는 방법은 존재합니다.

li = [1, 2, 3, 4, 5]

# Dequeue
a = li[:1]      # [1]
li = li[1:]     # [2, 3, 4, 5]

# Enqueue
li.append(6)

다음 예시 코드처럼 front에 있는 값을 dequeue를 할 수 있지만, 매번 메모리 공간을 새로 늘려야 하므로 메모리에 대한 소모가 발생합니다. 따라서 deque를 통해 추가적인 메모리를 사용하지 않고 O(1)의 시간복잡도로 dequeue를 수행할 수 있게 됩니다.