[Python/파이썬] 자료구조 - 큐(Queue)와 스택(Stack)

  이전 포스팅에서는 배열(Array)에 대해서 공부했다. 그 밖의 대표적인 자료구조로는 스택과 큐가 있다. 보통 스택과 큐라고 하면 LIFO, FIFO로 설명한다. 스택은 LIFO(Last In, First Out), 큐는 FIFO(First In, First Out)이라고 하고 한국어로는 후입선출, 선입선출을 의미한다. 즉, 데이터를 쌓아서 어떻게 출력할 것인가에 대한 자료구조이다.

 

 

 

1. 파이썬과 큐(Queue)

 

  서두에서 설명했지만 가장 먼저 입력 된 데이터가 가장 먼저 출력되는 구조이다. FIFO(First In, First Out)라고 부르기도 하며 반대로 LILO(Last In, Last Out)이라고 설명하기도 한다. 현실세계에서 식당에서 줄을 서는 경우를 큐의 예시로 들 수 있다. 먼저 줄을 선 순서대로 식당에 입장한다.

 

 

  큐에서 알아두어야 할 용어가 있는데 Enqueue(인큐), Dequeue(디큐)이다.

 

-. Enqueue : 큐에서 데이터를 입력하는 기능

-. Dequeue : 큐에서 데이터를 꺼내는 기능

 

  추가로 파이썬에서는 queue라는 내장 모듈을 제공한다. 아래 예시로 든 그림을 통해 코드를 작성해보았다. put( )은 큐에 데이터를 넣을 때 사용하는 메서드, get( )은 큐에서 데이터를 꺼내는 메서드이다

 

 

<코드>

import queue

#큐 모듈의 큐 클래스 객체 선언
data = queue.Queue()
print(type(data))

#선언 된 큐 객체에 3개 데이터 입력하기 : 2,5,8
data.put(2)
data.put(5)
data.put(8)

#큐 객체에서 입력된 객체 하나씩 꺼내기 :FIFO
print(data.get())
print(data.get())
print(data.get())

 

<결과>

<class 'queue.Queue'>
2
5
8

 

숫자 2,5,8을 순서대로 넣고 get( )을 3번 하면 먼저 입력 된 순서대로 출력된다.

 

 queue 내장 모듈 내에는 기본적인 Queue( ) 클래스 외에도 LifoQueue( ), PriorityQueue( ) 클래스가 존재한다. 여기서 자세히 다루진 않겠지만 LifoQueue( )는 스택과 같은 LIFO 구조, PriorityQueue( ) 는 사용자가 우선순위를 지정한대로 데이터를 꺼낼 수 있는 구조라고 보면 될 것 같다.

 

 

 

2. 파이썬과 스택(Stack)

 

  스택은 나중에 입력 된 데이터가 먼저 출력되는 LIFO(Last In, First Out) 자료 구조이다. 반대로 FILO(First In, Last Out)라고 부르기도 한다. 예시로 들만한게 하노이의 탑 게임을 들 수 있다. 하노이의 탑 게임에서는 스택과 같이 원판을 무조건 위에서부터 빼야 한다(마지막에 들어간 원판부터). 중간에서 빼는건 불가능하다.

 

  스택에서는 Push, Pop이라는 용어가 있다. 

 

-. Push : 데이터를 입력하기

-. Pop : 데이터를 꺼내기(마지막으로 입력 된 순서부터)

 

 

  위 그림을 파이썬으로 구현하려면 리스트를 선언해 append를 통해 데이터를 넣는다.(=Push)

꺼낼 때는 리스트의 pop( ) 함수를 사용하면 된다.

 

<코드>

#빈 리스트 선언
stack = []

#2,5,8 차례대로 리스트에 추가하기(=Push)
stack.append(2)
stack.append(5)
stack.append(8)

#값이 모두 입력된 리스트 출력하기
print("stack : ", stack)

#리스트 pop함수 통해 마지막으로 입력된 데이터 순 출력
print("첫번째 pop")
print(stack.pop())
print(stack)

print("두번째 pop")
print(stack.pop())
print(stack)

print("세번째 pop")
print(stack.pop())
print(stack)

 

<결과>

stack :  [2, 5, 8]

첫번째 pop
8
[2, 5]

두번째 pop
5
[2]

세번째 pop
2
[]

 

위 결과를 보면 알겠지만 pop( ) 한번 실행할 때마다 리스트의 마지막 요소가 출력되고 없어지는 것을 확인할 수 있다.

 

---

※ 참고자료 :  패스트 캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. 

자료구조 - 큐, 스택

https://fastcampus.co.kr/dev_online_algo