스택(Stack)/큐(Queue)/우선순위 큐(Priority Queue)/힙(Heap)

스택(stack)

삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조

• LIFO(Last In Frist Out)
  • 가장 마지막에 삽입된 데이터가 가장 먼저 나오는 구조
  • 삽입과 삭제가 한쪽에서만 일어남

💡 파이썬 스택(stack) 연산

• s.append(n): top 위치에 새로운 데이터(n)를 삽입
• s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인
• s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

큐(Queue)

삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조

• FIFO(First In First Out)
  • 가장 먼저 삽입된 데이터가 가장 먼저 나오는 구조
  • 삽입과 삭제가 양방향에서 이뤄짐

💡 파이썬 큐(queue) 연산

• s.append(n): rear 위치에 새로운 데이터(n)를 삽입
• s.popleft(): front 위치에 현재 있는 데이터를 삭제하고 확인
• s[0]: 큐의 맨 앞(front)에 있는 데이터를 확인하는 연산

 

우선순위 큐(priority queue)

값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

• 큐 설정에 따라 front에는 항상 최댓값 또는 최솟값이 위치
• 일반적으로 트리 종류 중 하나인 힙(heap)을 이용해 구현

from queue import PriorityQueue

💡 파이썬 우선순위 큐(priorityqueue) 연산

• q = PriorityQueue(maxsize=10): 비어있는 우선순위 큐를 초기화(maxsize: 최대 크기)
• q.put(n): 우선순위 큐에 데이터(n) 추가
• q.get(): 우선순위 큐에서 최솟값을 삭제한 뒤에 반환

 

힙(heap)

모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진트리

• 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본트리로 함
• 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙(기본)
• 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
• 키 값의 대소 관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 성립하지 않음

import heapq

💡 파이썬 힙(heap) 연산

• heapq.heappush(heap, item): heap을 유지하면서 item을 heap에 추가
• heapq.heappop(heap): heap에서 최솟값을 삭제한 뒤에 반환
• heapq.heapify(arr): 값이 들어 있는 리스트를 힙으로 변환

 

 

[문제 011] 스택으로 수열 만들기

스택 연산 수행 방법

1. 현재 수열 값 >= 자연수이면 스택에 자연수를 append
2. 현재 수열 값 < 자연수이면 pop 연산으로 스택에 있는 자연수를 꺼냄

n = int(input())
numlist = [int(input()) for _ in range(n)] # 수열을 이루는 n개의 수

answer = '' # push, pop 연산 과정
stack = []
i = 1
for num in numlist:        
    # num보다 작은 수는 모두 stack에 추가
    while i <= num:
        stack.append(i)
        answer += '+'
        i += 1
        
    # 스택의 마지막 원소와 num이 같으면 pop
    if stack and stack[-1] == num:
        stack.pop()
        answer += '-'
        continue

# 스택에 수가 존재하면 불가능한 경우이므로 NO 출력
if stack:
    print('NO')
else:
    for a in answer:
        print(a)

 

[문제 012] 오큰수 구하기

스택에 새로 들어오는 수(a)가 스택의 top에 존재하는 수(stack[-1][1])보다 크면 그 수는 오큰수

n = int(input())
A = list(map(int, input().split()))

nge = [-1 for _ in range(n)] # 오큰수를 저장할 배열
stack = []
for i, a in enumerate(A):
    # 스택의 마지막 원소보다 a가 크면 pop 연산 및 오큰수 저장
    while stack and stack[-1][1] < a:
        idx, value = stack.pop()
        nge[idx] = a
    
    stack.append((i, a)) # (인덱스, 원소) 형식으로 추가

print(*nge)

 

[문제 013] 카드 게임

1. popleft(): 제일 위에 있는 카드를 버림
2. rotate(-1): 남은 카드 중 제일 위에 있는 카드를 제일 밑으로 이동시킴
3. 1개의 카드가 남을 때까지 위 과정을 반복

from collections import deque

n = int(input()) # n장의 카드

queue = deque([i for i in range(1, n+1)])
for _ in range(n-1):
    queue.popleft() # 제일 위에 있는 카드를 버림
    queue.rotate(-1) # 남은 카드 중 제일 위에 있는 카드를 제일 밑으로 이동
    
print(queue[0])

 

[문제 014] 절댓값 힙 구현하기

정렬은 기준은 절댓값이므로 단순히 힙만을 구현해서는 안됨

• 데이터 삽입: (절댓값, 실제값)
• 절댓값을 기준으로 오름차순 정렬할 수 있도록 해줌
• 절댓값이 같으면 음수가 먼저 위치하도록 정렬해주어야 함

import sys
import heapq
input = sys.stdin.readline

n = int(input()) # n장의 카드
heap = []
for _ in range(n):
    x = int(input())
    if x != 0: # x가 0이 아니면 (절댓값, 실제값)으로 추가
        heapq.heappush(heap, (abs(x), x)) # 1. 절댓값 정렬 2. 같으면 실제값 기준 정렬
    else: # x가 0이면 절댓값이 가장 작은 값을 출력
        if heap:
            print(heapq.heappop(heap)[1])
        else: # 배열이 비여있으면 0을 출력
            print(0)

 

 

참고: Do it 알고리즘 코딩테스트: 파이썬 편