-
큐(Queue)와 스택(Stack)자료구조 2019. 11. 20. 14:03
큐(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
'자료구조' 카테고리의 다른 글
링크드 리스트(Linked List)_1 (0) 2019.11.28