[ 데이터구조 ] Stack, Queue

스택 (Stack)

스택 (Stack)

• LIFO (last-in first-out) : 가장 늦게 들어간 얘가 가장 먼저 나간다. e.g.) 돌탑쌓기
• 스택의 추상 데이터 타입 (Stack ADT)
  • 데이터 : 유한한 길이를 가지는 순서 리스트
  • 필수 연산
    • push : top에서 새로운 원소 삽입
    • pop : top에서 원소 빼내며 삭제
• Python의 list를 이용하여 구현할 수 있다.

• 구현예제

    stack = []
      
    # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
    stack.append(5)
    stack.append(2)
    stack.append(3)
    stack.append(7)
    stack.pop()
    stack.append(1)
    stack.append(4)
    stack.pop()
      
    print(stack) # 최하단 원소부터 출력
    print(stack[::-1]) # 최상단 원소부터 출력
  

재귀 함수 (recursive function)

• 재귀함수 사용시 꼭 종료조건을 설정해야 한다! (그렇지 않으면 무한 호출)
• 예시 : 팩토리얼, 유클리드 호제법
• 스택 구현 시 재귀함수를 이용하기도 한다.

큐 (Queue)

큐 (Queue)

• FIFO (first-in first-out) : 뒤로 들어와서 앞으로 나간다. e.g.) 한줄서기
• 큐의 추상 데이터 타입 (Queue ADT)
  • 데이터 : 유한한 길이를 가지는 순서 리스트
  • 필수 연산
    • enqueue : rear에서 새로운 원소 삽입
    • dequeue : front에서 원소 빼내며 삭제
• Python의 deque 라이브러리를 이용하여 구현할 수 있다.

• 구현예제

    from collections import deque 
      
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
      
    # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
    queue.append(5)
    queue.append(2)
    queue.append(3)
    queue.append(7)
    queue.popleft()
    queue.append(1)
    queue.append(4)
    queue.popleft()
      
    print(queue) # 먼저 들어온 순서대로 출력
    queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
    print(queue) # 나중에 들어온 원소부터 출력
  

우선순위 큐 (priority queue)

• 가장 높은 우선순위부터 삭제하는 큐
• 삽입할 때는 임의의 순서대로 진행.
• 들어올 땐 마음대로지만 나갈 땐 아니란다.

덱 (Deque)

• double ended queue
• 큐의 front와 rear에서 모두 삽입·삭제가 가능한 큐

• 파이썬 collections 모듈 내 deque

    from collections import deque
      
    deq = deque()
      
    # Add element to the start
    deq.appendleft(10)
      
    # Add element to the end
    deq.append(0)
      
    # Pop element from the start
    deq.popleft()
      
    # Pop element from the end
    deq.pop()