2. 파이썬의 큐와 스택

 

1. 큐의 구조
- 가장 먼저 넣은 데이터를 가장 먼저 꺼낼수 있는 구조이다.
- 줄을 서는 행위와 유사
- FIFO(First-in First-out)
참고 사이트 : (https://visualgo.net/en/list)

1-1.큐의 용어 
- Enqueue : 큐에 데이터를 넣는 기능
- Dequeue : 큐에 데이터를 꺼내는 기능 

1-2. 큐의 사용
- 푸시 메시지(순서대로 발송)
- 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현(운영체제) 


1-3. 파이썬 Queue 라이브러리를 활용하여 Queue 자료구조를 사용
- Queue() : 가장 일반적인 큐 자료구조를 생성
- LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조의 큐 자료구조를 생성(스택 구조와 비슷)
- PriorityQueue() : 데이터마다 우선순위를 넣어서 우선순위가 높은순으로 데이터를 출력

예시

1)
import queue
data_queue = queue.Queue()
data_queue.put('Hello') # Enqueue
data_queue.put('Python')
data_queue.put('Hello')
data_queue.put('World')
print(data_queue)
print(data_queue.qsize())
print(data_queue.get()) # Dequeue
print(data_queue.qsize())

-->
<queue.Queue object at 0x79c1310d5f30>
4
Hello
3


2)
for i in range(data_queue.qsize()):
    print(data_queue.get())
    
-->
Python
Hello
World


3)
# LifoQueue()로 큐 만들기
data_queue = queue.LifoQueue()
data_queue.put('Hello')
data_queue.put('Python')
data_queue.put('Hello')
data_queue.put('World')
print(data_queue.qsize())
print(data_queue.get())

-->
4
World


4)
# PriorityQueue()로 큐 만들기
data_queue = queue.PriorityQueue()
data_queue.put((10, '김사과')) # 키값이 작을수록 우선순위가 높음
data_queue.put((5, '반하나'))
data_queue.put((7, '오렌지'))
data_queue.put((2, '이메론'))
data_queue.put((8, '채리'))
print(data_queue.qsize())
print(data_queue.get())
print(data_queue.get())

-->
5
(2, '이메론')
(5, '반하나')


문제1
리스트 변수로 큐를 다루는 enqueue, dequeue 기능을 구현해보자

queue_list = list()

def enqueue(data):
    queue_list.append(data)

def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data


print(len(queue_list))
for index in range(10):
    enqueue(index)
-->
0


print(len(queue_list))
print(queue_list)
-->
10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print(dequeue())
-->
0
print(dequeue())
-->
1
print(queue_list)
-->
[2, 3, 4, 5, 6, 7, 8, 9]

 

2. 스택의 구조
- 가장 나중에 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
- 한쪽 끝에서만 자료를 넣거나 뺼 수 있는 구조
- LIFO(Last-in, First-out)

2-1. 스택의 용어
- push : 데이터를 스택에 쌓기
- pop : 데이터를 스택에서 꺼내기


2-2.스택의 사용
- 컴퓨터 내부의 프로세스 구조의 함수 동작 방식


### 2-3. 큐와 스택의 장단점
* 장점
    * 구조가 단순해서 구현하기 쉬움
    * 데이터 저장/읽기 속도가 빠름
* 단점
    * 데이터 최대 개수를 미리 정해야 함 -> 스택: 파이썬의 경우 재귀함수는 1000번까지만 호출이 가능
    * 저장 공간의 낭비가 발생할 수 있음 -> 미리 최대 개수만큼 저장공간을 확보해야 함

> 스택과 큐는 단순하고 빠른 성능을 위해 사용하므로 보통 배열 구조를 활용해서 구현하는 것이 일반적


# 파이썬 리스트 기능에서 제공하는 메소드로 스택 사용하기
data_stack = list()
print(data_stack)
-->
[]

data_stack.append(2)
data_stack.append(10)
data_stack.append(4)
data_stack.append(8)
print(data_stack)

-->
[2, 10, 4, 8]

data_stack.pop()
print(data_stack)

-->
[2, 10, 4]


#문제2
* 리스트 변수로 스택을 다루는 pop, push 기능을 직접 구현해보자
* 단, 리스트의 pop, push 함수는 사용하지 않음

stack_list = list()

def push(data):
    stack_list.append(data)

def pop():
    data = stack_list[-1]
    del stack_list[-1]
    return data

for index in range(10):
    push(index)

print(stack_list)
-->
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print(pop())
print(pop())
print(pop())
-->
9
8
7

print(stack_list)
-->
[0, 1, 2, 3, 4, 5, 6]