큐(Queue) & 스택(Stack)

큐 (Queue)

 

1. 큐 구조

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
  • 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일
  • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대

http://www.stoimen.com/blog/2012/06/05/computer-algorithms-stack-and-queue-data-structure/

 

2. 알아둘 용어

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

3. 파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기

• queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
• 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용
  • Queue(): 가장 일반적인 큐 자료 구조
  • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
  • PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

3.1. Queue()로 큐 만들기 (가장 일반적인 큐, FIFO(First-In, First-Out))

import queue

data_queue = queue.Queue()

data_queue.put("funcoding")
data_queue.put(1)

print(data_queue.qsize())   # 2
print(data_queue.get())     # funcoding
print(data_queue.qsize())   # 1
print(data_queue.get())     # 1
print(data_queue.qsize())   # 0

 

3.2. LifoQueue()로 큐 만들기 (LIFO(Last-In, First-Out))

import queue

data_queue = queue.LifoQueue()

data_queue.put("funcoding")
data_queue.put(1)

print(data_queue.qsize())	# 2
print(data_queue.get())		# LIFO이기 때문에 스택과 같아 funcoding이 나오는 것이 아니라 1이 나온다.

 

3.3. PriorityQueue()로 큐 만들기

import queue

data_queue = queue.PriorityQueue()

data_queue.put((10, "korea"))
data_queue.put((5, 1))
data_queue.put((15, "USA"))

print(data_queue.qsize())	# 3
print(data_queue.get())		# (5, 1)
print(data_queue.get())		# (10, 'korea')

 

참고: 어디에 큐가 많이 쓰일까?

• 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용된다. (운영체제 참조)

큐의 경우에는 장단점 보다는 (특별히 언급되는 장단점이 없음), 큐의 활용 예로 프로세스 스케쥴링 방식을 함께 이해해두는 것이 좋음

 

 

스택 (Stack)

 

1. 스택 구조

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

 

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

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

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

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

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

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

data_stack = list()

data_stack.append(1)
data_stack.append(2)

print(data_stack)		# [1, 2]
print(data_stack.pop())		# 2

 

 

 

 

 

[참고문헌]

패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online [자료구조 이론] 강의자료