This, Too, Shall Pass Away

1. 스택 구조

• 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 (데이터를 제한적으로 접근할 수 있음)
• LIFO(Last-In/First-Out) 구조 : 가장 마지막에 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
• FILO 구조

 * 큐(Queue)와 차이 : 큐 - FIFO구조 / 스택 - LIFO구조

2. 스택 특징

• 스택 활용 : 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• 장점 :

1) 구조가 단순하여 구현이 쉬움
2) 데이터 저장/읽기 속도가 빠름

• 단점(일반적인 스택 구현 시) :

1) 데이터 최대 갯수를 미리 정해야함
2) 저장공간 낭비 발생 가능성 있음

• 스택은 단순하고 빠른 성능을 위해 사용됨. 보통 배열 구조를 활용해서 구현하는 것이 일반적. 이 경우, 위의 단점들이 발생할 수 있음

3. 용어

• push() : 스택에 데이터 넣기
• pop() : 스택에서 데이터 꺼내기

4. 스택 사용

stack = [1,2,3]

# 데이터 넣기
def push(data): 
    stack.append(data)

# 맨 끝 데이터 추출
def pop(): 
    stack.pop()
    # del stack[-1] : pop() 메서드를 사용안 할 경우 del, 맨 끝 인덱스 -1 사용하기.

push(4)
print(stack) # 출력 화면 : [1, 2, 3, 4]
pop()
print(stack) # 출력 화면 : [1, 2, 3] -> pop()으로 인해 마지막에 넣은 4가 추출되었고 [1,2,3]만 남음

1. 큐 구조

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
•  웨이팅할 때, 가장 먼저 줄 선 사람이 가장 먼저 입장하는 것과 동일
•  FIFO(First-In / First-Out) : 가장 먼저 들어 간 데이터 가장 먼저 나옴
•  LILO(Last-In / Last-Out) : 가장 마지막으로 들어간 데이터 가장 마지막에 나옴

2. 용어

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

3. 파이썬 queue 라이브러리

• Queue() : 가장 일반적인 큐
• LifoQueue() : 나중에 들어간 데이터가 먼저 나오는 구조를 가진 큐(=스택)
• PriorityQueue() : 우선순위 큐, 데이터마다 우선순위도 넣어서 우선순위가 높은 순으로 데이터 나옴

4. Queue() 사용

import queue
queue_data = queue.Queue()

4-1) queue 데이터 삽입

queue_data.put("queue1")
queue_data.put("queue2")
queue_data.put("queue3")

4-2) queue 크기

queue_data.qsize()
# 출력 화면 : 3

4-3) queue 데이터 추출

queue_data.get()
# 출력화면 : queue1

'''
# 큐 순서대로 출력해보기
for i in range(queue_data.qsize()):
    print(queue_data.get())
# 출력 화면 :
queue1
queue2
queue3

queue_data.qsize()
# 출력 화면 : 0
'''

5. LifoQueue() 사용

import queue
queue_data = queue.LifoQueue()

5-1) LifoQueue 데이터 삽입 및 추출

queue_data.put("queue1")
queue_data.put("queue2")
queue_data.put("queue3")

queue_data.get()
# 출력 화면 : queue3

6. PriorityQueue() 사용

import queue
queue_data = queue.PriorityQueue()

6-1) PriorityQueue() 데이터 삽입 및 추출

import queue

queue_data = queue.PriorityQueue()

queue_data.put(5)
queue_data.put(2)
queue_data.put(10)

queue_data.get()
# 우선순위가 가장 높은(오름차순) 2를 반환
# 출력 화면 : 2

# * 튜플 형식으로 삽입했을때 (튜플의 0번째 인덱스를 우선순위로 여긴다.)
queue_data.put((5,"queue1"))
queue_data.put((1,"queue2"))
queue_data.put((10, "queue3"))

queue_data.get() 
# 우선순위 큐는 우선순위를 오름차순으로 하여 반환함 따라서 1이 들어간 튜플부터 반환.
# 출력 화면 : (1, 'queue2')

# 튜플의 1번째 인덱스 값을 가져오고싶을 때
queue_data.get()[1]
# 위에서 (1, 'queue2') 출력됐으므로 그 다음 우선순위인 5를 가지고있는 튜플을 가져와 그 튜플의 1번째 인덱스 값 반환
# 출력 화면 : queue1

7. list로 queue 다루기(enqueue, dequeue 기능 구현)

queue = [1,2,3,4,5]

def enqueue(data):
    queue.append(data) # .append() 함수를 사용하면 뒤에 데이터를 추가

def dequeue():
    queue.pop(0) # .pop(0) 함수를 이용하여 맨 앞의 데이터를 제거 -> * pop()은 맨 뒤 데이터 제거 괄호안에 맨앞 인덱스인 0 추가해줘야함
	# 또는 del queue[0]으로 써도 된다.
    
enqueue(6) 
print(queue) # 출력 화면 : [1, 2, 3, 4, 5, 6]
dequeue()
print(queue) # 출력 화면 : [2, 3, 4, 5, 6]

큐의사용

- 프로세스 스케쥴링 방식 구현

- 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조

- '파이썬'에서는 '리스트' 타입이 배열 기능을 제공

배열의 장점

• 인덱스로 빠르게 접근 가능

배열의 단점

• 배열을 구성할 땐 '길이'를 '미리' 설정해야한다는 점때문에 비효율적
• 새로운 데이터 삽입 시 크기 고정으로 인해 새로운 배열 만들어야함
• 데이터 중간에 삽입하거나 삭제 시 해당 데이터 뒤에 있는 데이터들의 위치를 이동시켜야함