큐(Queue)와 스택(Stack)

큐(Queue)

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
• FIFO(First In First Out)
• 큐 = 한 줄 서기 
• 먼저 들어온게 먼저 나간다.

Queue

 

알아둘 용어

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

 

파이썬 라이브러리 queue

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

 

Queue()

import queue

data_queue = queue.Queue()	# 일반적인 큐

data_queue.put('data')	# Enqueue
data_queue.put(1)	# Enqueue

data_queue.qsize()	# 큐의 사이즈 

data_queue.get()	# Dequeue

 

LifoQueue()

# Last in First out
import queue

data_queue = queue.LifoQueue()

data_queue.put('data')
data_queue.put(1)

data_queue.qsize()	# 2가 출력됨

data_queue.get()	# 1이 출력됨

 

PriorityQueue()

# 우선순위에 따라서 출력
import queue

data_queue = queue.PriorityQueue()

data_queue.put((10, 'data'))	# 튜플로 (우선순위, data) 입력
data_queue.put((5, 2))
data_queue.put((20, 100))

data_queue.qsize()

data_queue.get()	# (5, 2) 
data_queue.get()	# (10, 'data')

 

큐가 많이 사용되는 곳 ?

• 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨(운영체제 참조)
• 큐의 경우에는 장단점 보다는 큐의 활용 예로 프로세스 스케쥴링 방식을 함께 이해해두는 것이 좋음

 

이 부분은 이해가 잘안된다...ㅜㅜ

 

리스트 변수로 큐를 다루는 enqueue, dequeue 기능 구현

queue_list = list()

def enqueue(data):
	queue_list.append(data)
	
def dequeue(data):
	data = queue_list[0]
    del queue_list[0]	# 해당 리스트의 첫번째 제거
    return data

for i in range(10):
	enqueue(i)
	
len(queue_list)	
# 10

dequeue()	
# 0

 

 

스택(Stack)

• 데이터를 제한적으로 접근할 수 있는 구조
  • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
  
  • 스택 : LIFO

Stack

1. 스택 구조

• 스택은 LIFO(Last In, First Out) 또는 FILO 데이터 관리 방식을 따른다.
  • LIFO : 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
  • FILO : 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책
• 대표적인 스택의 활용
  • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• 주요 기능
  • push() : 데이터를 스택에 넣기
  • pop() : 데이터를 스택에서 꺼내기

 

2. 스택 구조와 프로세스 스택

• 스택 구조는 프로세스 실행 구조의 가장 기본
  • 함수 호출 시 프로세스 실행 구조를 스택과 비교해서 이해 필요

# 재귀 함수
def recursive(data):
	if data < 0:
		print("ended")
	else:
		print(data)
		recursive(data-1)
        print("returned", data)

recursive(3)

# 3
# 2
# 1
# 0
# ended
# returned 0
# returned 1
# returned 2
# returned 3
# 실행 순서에 대한 이해가 필요해보임!

 

3. 자료 구조 스택의 장단점

• 장점
  • 구조가 단순해서 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.
• 단점(일반적인 스택 구현 시)
  • 데이터 최대 갯수를 미리 정해야 한다.
    • 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능하다.
  • 저장 공간의 낭비가 발생할 수 있다.
    • 미리 최대 갯수만큼 저장 공간을 확보해야 한다.

 

• 스택은 단순하고 빠른 성능을 위해 사용되므로 보통 배열 구조를 활용해서 구현하는 것이 일반적임, 이 경우 위에서 열거한 단점이 있을 수 있다.

 

4. 파이썬 리스트 기능에서 제공하는 메서드로 스택 사용해보기

• append(push), pop 메서드 제공

data_stack = list()

data_stack.append(1)
data_stack.append(2)
# [1, 2]

data_stack.pop()
# 2

 

5. 프로그래밍 연습

• 리스트 변수로 스택을 다루는 pop, push 기능 구현해보기(pop, push 함수를 사용하지 않고 직접 구현해보기)

stack_list = list()

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

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

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

pop()
# 9