Python (11) - 스택(Stack)과 큐(Queue) 구현하기

우리가 자료구조를 공부함으로 복잡한 프로그램들을 편하게 설계할 수 있습니다. 기본적인 자료구조들을 넘어 중요한 두 가지 자료구조를 소개합니다. 바로 스택과 큐입니다.

 

시작하기 전에 개념 단어

자료구조에서 쓰는 단어 중 FIFO, FILO, LIFO, LILO이라는 단어가 있습니다.

• FIFO (First In First Out) : 먼저 데이터가 먼저 빠져나가는 구조 (큐)
• FILO (First In Last Out) : 먼저 데이터가 가장 마지막에 빠져나가는 구조 (스택)
• LIFO (Last In First Out) : 마지막 데이터가 가장 먼저 빠져나가는 구조 (스택)
• LILO (Last In Last Out) : 마지막 데이터가 마지막 나오는 구조 (큐)

 

스택 (Stack)

하노이탑 - Wikipedia

스택은 LIFO의 개념을 가지고 있으며 마지막에 넣은 데이터가 가장 먼저 빠져나가는 자료형입니다. 가장 쉬운 예시를 든다면 하노이탑에서 블록이 이동하는 원리와 같습니다. 블록을 이동할 때 가장 마지막에 둔 블록이 가장 먼저 이동합니다. 

해당 자료형을 이용하여, 웹브라우저의 뒤로가기, 재귀적인 알고리즘을 구현할 수 있습니다.

여담으로 재귀함수로 하노이탑 문제를 풀 수 있습니다.

스택 사진 설명

스택에서는 Push와 Pop이라는 두가지 기능을 사용합니다.

• Push : 데이터를 입력하기
• Pop : 데이터를 꺼내기

 

 

파이썬에서 리스트를 활용하여 구현할 수 있습니다. 리스트를 이용한 예시는 다음과 같습니다.

#EX1) Stack example

stack_ex = [] #빈 리스트 추가

#1,2,3 차례대로 Push
stack_ex.append(1)
stack_ex.append(2)
stack_ex.append(3)

#값이 모두 입력된 리스트 출력
print(stack_ex) #[1, 2, 3]

#리스트 자료형 안에 있는 데이터를 하나씩 Pop (LIFO)
stack_ex.pop()
print(stack_ex) #[1, 2]

stack_ex.pop()
print(stack_ex) #[1]

stack_ex.pop()
print(stack_ex) #[]

 

 

큐 (Queue)

터널 - pixabay

큐는 FIFO의 개념을 가지고 있으며 먼저 넣은 데이터가 가장 먼저 빠져나가는 자료형입니다. 운전을 할 때 터널 구간에서는 먼저 들어가는 차가 먼저 터널을 통과합니다. 해당 원리와 같습니다. 해당 자료형을 이용하여 프린터 출력, 은행에서 고객 대기표등을 사용할 수 있습니다. 

큐 사진 설명

큐에서는 Enqueue, Dequeue라는 두가지 기능을 사용합니다.

• Enqueue : 큐에서 데이터를 입력하는 기능
• Dequeue : 큐에서 데이터를 꺼내는 기능

 

파이썬에서는 큐 모듈이 존재합니다. 해당 모듈을 사용하여 파이썬으로 구현한 예시를 구현했습니다.

#EX2) Queue example
import queue

queue_ex = queue.Queue() #큐 객체 선언

#1,2,3 차례대로 Enqueue
queue_ex.put(1)
queue_ex.put(2)
queue_ex.put(3)

#큐에는 지금 1,2,3이 순서대로 저장되어있다.

#큐에 입력된 데이터 Dequeue (FIFO)
print(queue_ex.get()) #1
print(queue_ex.get()) #2
print(queue_ex.get()) #3