자료구조 기초 - 스택(Stack)과 큐(Que)

탐색 (Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.

 

프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는  문제를 자주 다루게 된다.

 

대표적인 탐색 알고리즘으로 DFS(Depth-First Search)와 BFS(Breadth First Search)를 꼽을 수 있는데, 이 둘을 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한  이해가 전제되어야 하므로 사전 학습으로 스택과 큐, 재귀 함수를 간단히 정리하고자 한다.

 

자료구조 (Data Structure) 란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 그 중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심  적인 함수로 구성된다.

 

• 삽입(Push) : 데이터를 삽입한다.
• 삭제(Pop) : 데이터를 삭제한다.

물론 실제로 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야 한다.

 

오버플로(Overflow)는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생합니다. 즉, 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생한다.

 

반면에 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 언더플로(Underflow)가 발생합니다.

 

 

---

 

스택(Stack)

스택(Stack)은 박스 쌓기에 비유할 수 있습니다. 흔히 박스는 아래에서부터 위로 차곡차곡 쌓게 됩니다.

그리고 아래에 있는 박스를 지우기 위해서는 위에 있는 박스를 먼저 내려야 합니다. 이러한 구조를 선입후출 구조 또는

후입선출 구조라고 합니다.

 

 

✔ 스택의 특징

스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.

 

top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.

 

스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.

 

스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다.

 

따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다.

 

이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.

 

 

✔ 스택의 활용 예시

스택의 특징인  후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.

 

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

 

💬 예시

stack = []

stack.append(5)
print(stack)

stack.append(2)
print(stack)

stack.append(3)
print(stack)

stack.append(7)
print(stack)

stack.pop()
print(stack)

stack.append(1)
print(stack)

stack.append(4)
print(stack)

stack.pop()

print(stack)  # 최 하단 원소부터 출력
print(stack[::-1])  # 최 상단 원소부터 출력

 

결과 :

 

파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없습니다.

 

기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와  동일하게 동작합니다.

append() 메서드는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문입니다.

 

---

큐(Que)

큐(Queue)는 대기 줄에 비유할 수 있습니다.

 

우리가 흔히 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 됩니다. 물론 새치기는 없다고 가정하겠습니다.

 

나중에 온 사람일 수록 나중에 들어가기 때문에 흔히 ‘공정한’ 자료구조라고 비유됩니다. 이러한 구조를 선입선출 구조 라고 합니다.

 

 

✔ 큐의 특징

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

 

이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행된다.

 

이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue), 프론트에서 이루어지는 삭제연산을 디큐(deQueue)라고 부른다.

 

• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성
• 접근방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

즉, 큐에서 Front 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며, Rear 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

 

 

 

✔ 큐의 활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

 

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

출처: https://devuna.tistory.com/22 [튜나 개발일기]

 

 

💬 예시

from collections import deque
# 큐 구현을 위해 deque 라이브러리 사용

queue = deque()

#삽입(5) – 삽입(2) – 삽입(3) – 삽입(7) – 삭제 () – 삽입(1) – 삽입(4) – 삭제()  
queue.append(5)
print(queue)

queue.append(2)
print(queue)

queue.append(3)
print(queue)

queue.append(7)
print(queue)

queue.popleft()
print(queue)

queue.append(1)
print(queue)

queue.append(4)
print(queue)

queue.popleft()

print(queue)

queue.reverse()  
print(queue)

결과 :

 

파이썬으로 큐를 표현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용한다.

deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다.

 

더불어 대부분의 코딩 테스트에서는 collections 모듈과 같은 기본 라이브러리 사용을 허용하므로 사용해도 좋을 것 같다.