[자료구조] 큐 Queue, 스택 Stack

큐 Queue

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
• FIFO(First In First Out), LILO(Last In Last Out)
• 운영체제 멀티 태스킹을 위한 프로세스 스케줄링 방식 구현에 많이 쓰임
• 큐의 기능
  • Enqueue : 큐에 데이터 넣기
  • Dequeue : 큐에서 데이터 꺼내기

 

파이썬 Queue 라이브러리

• Queue() FIFO , LifoQueue() LIFO, PriorityQueue() 우선순위

Queue

• Enqueue = put, dequeue = get

import queue

queue = queue.Queue()

queue.put("test")
queue.put(1)

Output
queue.qsize()
2
queue.get()
test
queue.get()
1

LifoQueue (Stack기능)

import queue

queue = queue.LifoQueue()

queue.put("test")
queue.put(1)

Output
queue.qsize()
2

# 이 부분이 달라짐
queue.get()
1
queue.get()
test

PriorityQueue

• put((우선순위, 값))

import queue

queue = queue.PriorityQueue()

queue.put((10,"test"))
queue.put((5,1))
queue.put((1,"song"))

Output
queue.get()
(1, 'song')
queue.get()
(5, 1)

 

---

스택 Stack

• 데이터를 제한적으로 접근할 수 있고 한쪽 끝에서만 자료를 넣거나 뺼 수 있음
• 가장 나중에 넣은 데이터를 가장 먼저 뺄 수 있음 (LIFO Last in first out, FILO)
•  스택 활용
  • 컴퓨터 내부 프로세스 구조의 합수 동작 방식에 쓰임
• 장점
  • 구현이 쉬움
  • 데이터 저장, 읽기 속도가 빠름
• 단점
  • 데이터 최대 갯수를 정해야 함 (파이썬의 경우 재귀 함수는 1000번까지 호출 가능)
  • 저장공간 낭비가 있을 수 있음
• 스택의 기능
  • Push : 스택에 데이터 넣기
  • Pop : 스택에 데이터 빼기

재귀 함수를 통해 스택 이해하기(프로그램 실행 구조 기본)

def recursive(data):
    if data<0:
        print("end")
    else:
        print(data)
        recursive(data-1)
        print("reture",data)
        
recursive(2)

Output
2
1
0
end
reture 0
reture 1
reture 2

파이썬 List Stack method

stack = list()
stack.append('a')
stack.append('b')
stack.append('c')

Output
print(stack)
['a', 'b', 'c']
stack.pop()
'c'
print(stack)
['a', 'b']