🟠 스택과 큐

🐰 스택

스택: 삽입과 삭제 연산이 후입 선출(Last In First Out)로 이뤄지는 자료구조
top: 삽입과 삭제가 일어나는 위치를 뜻한다.
s.append(data) : top위치에 새로운 데이터 삽입하는 연산
s.pop(data) : top위치에 현재 있는 데이터를 삭제하고 확인하는 연산
s[-1]: top위치에 현재 있는 데이터를 단순 확인하는 연산

깊이 우선 탐색(Depth First Search)/, 백트래킹 종류 코딩테스트에 효과적!

🐰 큐

삽입과 삭제 연산이 선입선출(First In First Out)로 이뤄지는 자료구조
rear: 큐에서 가장 끝 데이터를 가리키는 영역 (새 값 추가는 큐의 rear에서 이루어짐)
front: 큐에서 가장 앞의 데이터를 가리키는 영역 (삭제는 큐의 front에서 이루어짐)
s.append(data): rear부분에 새로운 데이터 삽입 하는 연산
s.popleft(): front부분에 있는 데이터를 삭제하고 확인하는 연산
s[0]: 큐의 맨 앞(front)에 있는 데이터를 확인할때 사용하는 연산

큐는 너비 우선 탐색(BFS: Breadth First Search)에서 자주 사용!

🐰 우선순위 큐

값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조!
큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치함.

우선순위 큐는 일반적으로 힙(heap)이용해 구현함- 트리 종류 중 하나!

🦊 [문제] : 오큰수 구하기

백준 17298번

🐙 [코드]

n = int(input())
ans = [0] * n
A = list(map(int, input().split()))
myStack = []

for i in range(n):
  while myStack and A[myStack[-1]] < A[i]: # 오큰수 조건
    ans[myStack.pop()] = A[i]. # 정답 리스트에 오큰수 저장
    myStack.append(i)

while myStack:
  ans[myStack.pop()] = -1

result = " "
for i in range(n):
  result += str(ans[i])+ " "
  
print(result)