파이썬 자료구조 (2) 큐와 스택

1. 큐의 구조

• FIFO(First-In, First-Out): 먼저 넣은 데이터를 먼저 꺼낼 수 있는 구조 
• 한쪽 끝에서 요소가 추가되고 다른쪽 끝에서 요소가 제거되는 선형 데이터 구조
• 참고 사이트: https://visualgo.net/en/list

 

1-1. 큐의 용어

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

 

1-2. 큐의 사용

• 어떠한 작업/데이터를 순차적으로 실행/사용하기 위해 대기 시킬 때 사용
• 멀티테스킹을 위한 프로세스 스케줄링 방식을 구현(운영체제)

 

1-3. 파이썬 queue 라이브러리를 활용하여 queue 자료구조 사용

• Queue(): 가장 일반적인 큐 자료구조
• LifoQueue(): 나중에 입력된 데이터가 먼저 출력(LIFO)되는 구조의 큐 자료구조로 스택 구조와 유사
• PriorityQueue(): 데이터마다 우선 순위를 넣어서 우선 순위가 높은 순으로 데이터를 출력

import queue

# 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())

for i in range(data_queue.qsize()):
    print(data_queue.get())
    
# 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())

# 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())

# 리스트 변수로 큐를 다루는 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)

print(len(queue_list))
print(queue_list)

print(dequeue())
print(dequeue())
print(queue_list)

 

 

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) 	# push
data_stack.append(10)
data_stack.append(4)
data_stack.append(8)
print(data_stack)

data_stack.pop()	# pop
print(data_stack)

# 리스트 변수로 스택을 다루는 pop, push 기능 구현하기 (단, 리스트 pop push 함수 사용 금지)

stack_list = list()

def stackPush(data):
	stack_list.append(data)
    
def stackPop():
	data = stack_list[-1]
    del stack_list[-1]
    return data
    
print(len(stack_list))

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

print(len(stack_list))
print(stack_list)

print(stackPop())
print(stack_list)