[자료구조] 스택(Stack)과 큐(Queue) 데크(Deque)까지 (Python)

설명

---

자료구조(Data Structure)를 공부할 때 가장 처음 접하는 것은 스택(Stack)과 큐(Queue)다.

 

그전에 자료구조란 Data를 효율적으로 저장하고 접근하여 사용하는 방법을 뜻한다.

 

적합한 상황에 적절한 자료구조를 사용하면 아주 효율적인 알고리즘을 사용할 수 있는 장점이 있다.

 

이번 시간에 가장 기본 중에 기본인 스택과 큐에 대해 알아보겠다.

 

스택 (Stack)

---

먼저 스택은 나중에 들어오는 Data가 먼저 나가는 LIFO(Last In First Out) 형태이다.

 

통에다가 블록을 넣고 빼는 방식을 연상하면 이해가 쉬울 것이다.

 

Data를 넣는 연산은 Push라고 한다.

 

Push 연산 결과

 

반대로 Data를 빼는 연산은 Pop이라고 한다.

 

Pop 연산 결과

 

그림을 통해 쉽게 이해할 수 있듯이 나중에 들어간 Data가 먼저 나오고 먼저 들어간 Data가 나중에 나오는 자료구조를 스택이라고 표현한다.

 

만약 C 같이 다른 언어였다면 구조체를 선언하여 현재 얼마나 Data가 들어왔는지 판단하는 Top이란 변수를 통해 구현하겠지만 Python은 그럴 필요가 없다.

 

보통 라이브러리를 사용하는 경우를 제외하면 구현의 편의성을 위해 배열을 미리 선언(정적 할당)하고 잘못된 인덱스로 접근하는 Index Error를 방지하기 위해 Top이란 변수를 선언하여 오류를 방지한다.

 

또한 필요하다면 배열의 크기를 변경하는 복잡한 과정을 거쳐야 한다.

 

하지만 Python은 배열이 아닌 리스트를 지원하기 때문에 비교적 Data 추가 삭제에 대한 고민을 덜 수 있다.

 

큐 (Queue)

---

다음은 큐다.

 

큐는 먼저 들어온 Data가 먼저 나가는 FIFO(First In First Out) 형태이다.

 

즉, 차례대로 줄을 서서 기다리는 형태를 생각하면 된다.

 

큐에서 Data를 넣는 연산은 Enqueue라고 한다.

 

Enqueue 연산 결과

 

Data를 빼는 연산은 Dequeue라고 한다.

 

스택과는 다르게 먼저 들어간 Data가 먼저 빠지는 것을 확인할 수 있다.

 

Dequeue 연산 결과

 

구현

---

Python은 앞서 말한 대로 배열이 아닌 리스트를 지원하기 때문에 리스트와 관련되어 지원하는 함수들로 아주 쉽게 스택과 큐를 구현 가능하다.

 

여러 가지 함수들이 있지만 구현하는데 필요한 함수는 append()와 pop()이다.

 

각각 뒤에 원소를 추가하고 빼는 함수인데 pop(x)처럼 안에 인자를 넣으면 x번째 원소를 반환하고 제거한다는 의미이다.

 

이를 이용하여 x에 0을 넣으면 0번째 원소를 제거하므로 쉽게 큐를 구현할 수 있다.

 

다음은 앞서 설명한 과정을 그대로 구현한 전체 코드이다.

 

stack=[]    #스택 선언
print("현재 스택 :",stack)
stack.append(1)     # 1 추가
print("현재 스택 :",stack)
stack.append(2)     # 2 추가
print("현재 스택 :",stack)
stack.pop()         #끝 원소 하나 제거
print("현재 스택 :",stack)
stack.pop()         #끝 원소 하나 제거
print("현재 스택 :",stack, end="\n\n")

queue=[]    #큐 선언
print("현재 큐 :",queue)
queue.append(1)     # 1 추가
print("현재 큐 :",queue)
queue.append(2)     # 2 추가
print("현재 큐 :",queue)
queue.pop(0)         #첫 원소 하나 제거
print("현재 큐 :",queue)
queue.pop(0)         #첫 원소 하나 제거
print("현재 큐 :",queue)

 

결과 화면

 

복잡한 과정 없이 함수 두 개로 간단하게 구현하였으며 보통 그래프 탐색에서 스택은 깊이 우선 탐색(DFS), 큐는 너비 우선 탐색(BFS)에 자주 쓰인다.

 

따라서 코테준비를 위해 상당히 자주 사용할 문법이므로 알아야 한다.

 

데크 (Deque)

---

사실 큐는 구현 방법에 따라 다양한 이름이 있는데 가장 단순한 큐(Queue), 배열의 비효율성을 개선하기 위한 원형 큐(Circular Queue), 앞과 뒤 둘 다 Data를 넣고 뺄 수 있는 데크(Deque), 자료구조 중 하나인 힙(Heap)을 이용한 우선순위 큐(Priority Queue) 이런 식으로 장단점을 개선한 방식이 존재한다.

 

Python의 특성 상 원형 큐는 구현할 필요가 없고 우선순위 큐는 파이썬의 모듈 중 하나인 heapq를 사용하면 된다.

 

이번에 추가적으로 설명할 자료구조는 데크다.

 

데크 혹은 덱이라 부르는데 이 자료구조는 앞과 뒤에서 Enqueue와 Dequeue가 가능하다.

 

Deque 연산

 

파이썬의 pop()은 O(1)의 시간 복잡도가 들지만 첫 번째 원소를 제거하기 위해 pop(0)을 사용하게 되면 끝에서부터 원소를 찾기에 O(n)의 시간 복잡도가 걸린다.

 

따라서 Input이 너무 큰 상황이라면 효율을 위해 데크를 사용하여 시간 복잡도를 줄일 수 있다.

 

주요 함수는 append(), appendleft(), pop(), popleft()이고 left가 붙으면 첫 번째에, 붙지 않으면 마지막에 적용된다.

 

데크 구현

---

다음은 데크의 연산 과정을 확인할 수 있는 전체 코드이다.

 

from collections import deque   #데크 모듈 선언
deque=deque()
print("현재 데크 :",deque)
deque.append(1)         #오른쪽에 1 추가
print("현재 데크 :",deque)
deque.appendleft(2)     #왼쪽에 2 추가
print("현재 데크 :",deque)
deque.popleft()         #첫 번째 원소 제거
print("현재 데크 :",deque)
deque.pop()             #끝 원소 제거
print("현재 데크 :",deque)

 

결과 화면

 

처음 보면 모듈 선언이 다소 어려울 수 있겠지만 익숙해진다면 그냥 리스트로 구현하는 것보다 시간 복잡도적으로 유리한 구현이 가능해진다.

 

스택과 큐를 연습할 수 있는 문제를 추천하며 마무리 짓겠다.

 

https://www.acmicpc.net/problem/10828

10828번: 스택

 

https://www.acmicpc.net/problem/10845

10845번: 큐