자료구조-스택과 큐

이론

📖 스택
삽입과 삭제가 후입선출(LIFO : Last-In First-Out)로 이루어진 자료구조이다.
삽입과 삭제가 한 쪽에서만 일어난다.

📖 큐
삽입과 삭제가 선입선출(FIFO : First-In First-Out)로 이루어진 자료구조이다.
삽입과 삭제가 양방향에서 이루어진다.

문제풀이

📖 백준 17298 (백준 17298 문제)

✏ 반복문x, 스택을 이용해서 푼다.

✏ 스택에 입력되는 수가 top에 존재하는 수보다 크면 그 수는 오큰수다.
오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자마다 -1을 출력한다.

• 스택이 채워져있고, test[index] > test[top] 인 경우 pop한 인덱스를 통해 정답리스트에 오큰수를 저장한다.
• for문을 다 돌고나서, 스택이 비어있지 않을 경우 스택이 빌 때까지 정답리스트의 남은 인덱스들에 -1을 넣는다.
• 정답리스트의 값들을 출력한다.

📍 시간초과에 유의하자!!!

import sys
input = sys.stdin.readline

n = int(input())
test = list(map(int, input().split()))
result = [0] * n
stack = []
nge = ""

for i in range(n):
	# 스택이 비어있지않고 현재 수열이 스택 top인덱스가 가리키는 수열보다 큰 경우
	while stack and test[stack[-1]] < test[i]:
		# 정답리스트에 오큰수를 현재수열로 저장
		result[stack.pop()] = test[i]
	stack.append(i)

# 스택비어있지 않을경우 -1 출력
while stack:
	result[stack.pop()] = -1

for i in range(n):
	sys.stdout.write(str(result[i])+ " ")

📖 백준 2164 (백준 2164 문제)

✏ 큐를 이용한다.
가장 위에 있는 카드를 가장 아래로 옮기는 것은 큐의 선입선출을 이용하여 코드를 작성할 수 있다.

#큐 사용
#popleft()로 맨 위 카드를 버리고, popleft()->append()를 사용하여 맨 위의 카드를 아래로 이동시킨다.

from collections import deque
import sys
input=sys.stdin.readline

n=int(input())
queue=deque()

for i in range(1,n+1):
	queue.append(i)

while len(queue)>1:
	queue.popleft()
	queue.append(queue.popleft())

print(queue[0])

📖 백준 11286 (백준 11286 문제)

✏ O(nlogn) 시간복잡도알고리즘을 사용.
n의 최대범위가 100,000이므로 제한시간이 초과되지않게, O(nlogn) 시간복잡도 알고리즘을 사용한다.

✏ 우선순위 큐를 사용.
우선순위 큐의 정렬기준은 직접 정의한다.

• x==0 일 때, 큐가 비어있으면 0을 출력하고 비어있지않으면 큐의 front값을 get()을 이용해서 출력한다.
• x!=0 일 때, 새로운 값을 큐에 추가하고 우선순위 큐 정렬기준을 이용해 자동정렬한다.

#절댓값 힙
#우선순위 큐 - 정렬기준 직접 정의

from queue import PriorityQueue
import sys
input=sys.stdin.readline
print=sys.stdout.write

n=int(input())
queue=PriorityQueue()

for i in range(n):
	x=int(input())
	if(x==0):
		if(queue.empty()):
			print("0\n")
		else:
			temp=queue.get()
			print(str(temp[1])+"\n")
	#1)절댓값 기준 정렬 2)음수
	else:
		queue.put((abs(x),x))

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준