[파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

스택(Stack)

 

스택이란?

 

 스택은 후입선출의 자료구조로 LIFO(Last In First Out)라고 불리기도 합니다. 실생활에서 예를 들어볼까요?

우리가 보통 접시를 선반에 차곡차곡 쌓아올린 후 쌓여있는 접시에서 접시를 꺼낼때는 가장 위에 있는 접시를 꺼내어 결국 마지막에 올린 접시를 먼저 꺼내는 구조가 됩니다. 여기서 접시를 데이터로 비유하면 이해하기 편합니다!

 

 이러한 스택 자료구조는 컴퓨터 메모리 공간에서 함수 호출과 관계되는 여러 변수들이 저장되는 데 사용되고, 데이터 처리 알고리즘에서도 중요하게 사용되니 잘 알아두도록 합시다!

 

스택의 구조

스택의 전반적인 구조

 위의 접시로 예를 들었듯이 스택 자료구조는 맨 위에서만 데이터를 삽입하고 삭제하는 것이 가능합니다. 데이터 더미에서 데이터를 삽입하는 연산을 push라 하고, 데이터를 삭제하는 연산을 pop이라고 합니다. 위와 같은 상태에서 Data3을 삽입하고 삭제하는 과정을 보여드리겠습니다.

스택 Push

데이터를 삽입하는 연산 push를 통해 Data3을 삽입했습니다. 보이는 것처럼 Data3은 제일 위에 놓이게 됩니다.

스택 Pop

데이터를 삭제하는 연산 Pop을 통해 Data3을 삭제했습니다. 마찬가지로 제일 위에 있는 데이터인 Data3이 삭제됩니다. 

 

스택 구현

 

C언어를 공부해보신 분 들은 알겠지만 이와 같은 스택 구조를 사용하기 위해서는 스택을 직접 구현을 해야합니다. 하지만 파이썬에서는 따로 구현하지 않고, 리스트의 내장 함수를 사용하여 스택을 사용할 수 있습니다.

 

push -> append

pop -> pop

 

위와같이 push연산은 append함수로 pop연산은 pop함수로 사용하면 됩니다. 이해를 위해 코드로 직접 보여드리겠습니다.

코드

#스택
stack = [1, 2, 3, 4, 5]
#append 함수를 사용하여 6 push
stack.append(6)
#append 함수를 사용하여 8 push
stack.append(8)
#pop 함수를 사용하여 8 pop
stack.pop()
#결과 확인
print(stack)

 

실행 결과

이미 스택에는 1, 2, 3, 4, 5 총 5개의 데이터가 있었고, 6, 8을 push했다가 pop을 했으므로 남아있는 데이터는

1, 2, 3, 4, 5, 6이 됩니다.

 

스택 활용

• 재귀 알고리즘 
• DFS(Depth First Search) 알고리즘
• 웹 브라우저 뒤로가기
• 문자열 역순 출력

---

큐(Queue)

 

큐란?

 

 큐는 스택과 달리 선입선출의 자료구조로 FIFO(First In First Out)라고 불리기도 합니다. 큐는 은행에서 대기표를 뽑고 순서를 기다리는 것을 예로 들 수 있습니다. 먼저 대기표를 뽑은 순서로 서비스를 받게됩니다. 이때 이 대기하는 사람들을 데이터로 비유하면 이해하기 쉽습니다.

 

 이러한 큐 자료구조는 캐시(Cache)에도 사용되고, 스택과 마찬가지로 데이터 처리 알고리즘에서 중요하게 사용됩니다!

 

큐의 구조

큐의 전반적인 구조

 위의 은행에서의 대기하는 사람들을 예로 들었듯이 데이터는 뒤에서 들어오고, 앞에서 처리가 됩니다. 큐로 데이터를 삽입하는 연산을 enqueue라고 하고, 큐에서 데이터를 처리하는 연산을 dequeue라고 합니다. 위와 같은 상태에서 연산을 사용해 데이터 구조가 어떻게 바뀌는지 보겠습니다.

 

큐 Enqueue

Enqueue 연산을 사용해서 Data3을 큐에 삽입했습니다. Data3은 데이터들의 제일 뒤에 놓이게 됩니다.

 

큐 Dequeue

스택과 달리 dequeue 연산이 앞에서 사용되기 때문에 맨 앞에 있던 Data1이 처리가 됩니다. 은행에서 대기하는 사람을 연상하면 쉽게 이해가 되죠? ㅎ

 

큐 구현

스택과 마찬가지로 따로 구현하지 않지만, 파이썬에서 제공해주는 라이브러리 deque를 사용해서 큐를 구현합니다.

 

Enqueue -> append

Dequeue -> popleft

 

 따지고 보면 리스트로도 큐를 구현할 수 있지만 시간복잡도에서 차이가 납니다. 만약 리스트에서 dequeue 연산을 구현하기 위해 pop(0) 함수를 사용하여 0 인덱스의 값을 처리할 수 있지만 모든 원소를 앞으로 복사해야 하기 때문에 O(n)의 시간이 걸립니다. 하지만 deque 자료구조는 내부적으로 Double Linked List로 구현되어 있어서 양 끝 추가/ 삭제 연산시 O(1)의 시간이 걸립니다.

 

코드

#큐
#라이브러리 임포트
from collections import deque
queue = [1, 2, 3, 4, 5]
queue = deque(queue)
#append 함수를 사용하여 6 enqueue
queue.append(6)
#append 함수를 사용하여 8 enqueue
queue.append(8)
#popleft 함수를 사용하여 1 dequeue
queue.popleft()
#결과 확인
print(queue)

 

실행 결과

이미 큐에는 1, 2, 3, 4, 5 총 5개의 데이터가 있었고, 6, 8을 enqueue했다가 dequeue를 했으므로 남아있는 데이터는

2, 3, 4, 5, 6, 8이 됩니다.

 

큐 활용

• Cache 구현
• BFS(Breadth First Search) 알고리즘
• 프로세스 관리

---