코린이형준

큐(Queue)

1.구조

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

2.알아둘 용어

• FIFO
• Enqueue: 큐에 데이터를 넣는 용어
• Dequeue: 큐에서 데이터를 꺼내는 용어

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

#일반적인 큐 사용(fifo)
import queue

data_queue = queue.Queue()
data_queue.put("func")
data_queue.put(1)
data_queue.get() # func 출력
data_queue.get() # 1 출력
#들어간 순서대로 출력됨 FIFO

#LifoQueue(Lifo(Lastin,Firstout)) 
import queue
data_queue = queue.LifoQueue()
data_queue.put(123)
data_queue.put(456)
data_queue.get() # 456출력
data_queue.get() # 123출력
#나중에 들어간 456출력 LIFO


#PriorityQueue(우선순위에 따라추출중요!!)
import queue
data_queue = queue.PriorityQueue()
data_queue.put((10,"korea"))
data_queue.put((5,32))
data_queue.put((7,"china"))
data_queue.get() # 32출력
#가장 우선순위가 높은 32가 출력됨

4.직접 dequeue, inqueue구현해보기

#dequeue, inqueue 구현
queue_list = list()

def enqueue(data):
    queue_list.append(data)
    
def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data

스택(stack)

1.구조

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

  • 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
    
    # recursive(data-1)의 종결과 같은 ended가 출력된이후 
    # 쌓여있는 returned 출력문을 가장 늦게 들어왔지만 0부터 출력해냄

2.알아둘 용어

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

3.스택의 장단점

• 장점
  • 구조가 단순해서 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.
• 단점
  • 데이터 최대 갯수를 미리 정해야 한다.(파이썬의 경우 재귀함수는 1000번까지 호출가능)
  • 저장공간의 낭비가 발생할 수 있다.(미리 최대 개수만큼 저장 공간을 확보해야함)
• 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는것이 일반적임.

4. 파이선 리스트 기능에서 제공하는 메서드 스택

• append(push), pop

• data_stack = list()
  data_stack.append(1)
  data_stack.append(2) # [1,2]
  data_stack.pop() # 2 출력 [1]

5.직접 push, pop 구현해보기

stack_list =list()
def push(data):
    stack_list.append(data)
    
def pop():
    data = stack_list[-1]
    del stack_list[-1]
    return data