⭐️ 스택 / 큐 / 덱⭐️
자료구조의 일종
스택 - 후입선출(LIFO, Last-In-First-Out) 구조
가장 마지막에 삽입된 자료가 가장 먼저 삭제된다
위치
top : 삽입(push)과 삭제(pop)가 일어나는 위치
연산
list.append(data) : top에 새로운 데이터를 삽입하는 연산이다.
list.pop(): top 위치의 데이터 삭제/확인\
list[-1] : top 위치의 데이터를 확인
- 깊이 우선 탐색 알고리즘
- 백트래킹 분야 (역순출력 등)
큐 - 선입선출(FIFO, First in first out) 구조
가장 먼저 삽입된 자료가 가장 먼저 삭제된다
+(deque이용)
위치
rear : 가장 끝 데이터(마지막에 넣은 데이터)
front : 가장 앞의 데이터
연산
list.append(data) : rear에 새로운 데이터를 삽입하는 연산이다. (끝에)
list.popleft(): front 위치의 데이터 삭제/확인
list[0] : front위치의 데이터를 확인
- 너비 우선 탐색 알고리즘 등
+ 우선순위 큐 PriorityQueue : 들어간 순서와 상관 없이 우선순위(최솟값/최댓값)가 높은 데이터가 먼저 나옴
덱
양쪽 front, rear 에서 삽입 삭제가 모두 가능한 큐를 의미하는 자료구조이다.
deque - collections 모듈
스택/큐로 사용 가능!
1번 - 백준 1874번 / 실버 3
스택
1) 현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 푸쉬 -> 푸쉬가 끝나면(크거나 같음) 마지막 1회만 pop!
2) 현재 수열 값이 자연수보다 크다면 pop으로 스택에 있는 값을 꺼냄. 꺼낸 값이 현재 수열 값(목표)가 아닐 시 NO 출력(표현 불가)
(자연수는 다음으로 스택에 넣을 수 있는 값임)
from sys import stdin
N = int(stdin.readline())
stack = []
answer = []
cha = 1
k = True
for i in range(1,N+1): # 1부터 N까지
num = int(stdin.readline())
while(cha<=num):#수 나올때까지 스택 쌓기
answer.append("+")
stack.append(cha)
cha += 1
if stack[-1] == num:# 같을 때
stack.pop()
answer.append("-")
else:
k = False
print("NO")
break
if k == True:
for cha in answer:
print(cha)
2번 - 백준 17298번 / 골드4
스택
from sys import stdin
N = int(stdin.readline())
Nlist = list(map(int,stdin.readline().split()))
myStack = []
answer = [0 for _ in range(N)]
for i in range(N):
# 스택이 비었을 때 예외 처리 / 새로 들어오는 값(오른쪽에 있는값)이 해당 값보다 크면 해당값의 오큰수가 될 수 있음.
while(myStack and Nlist[myStack[-1]] < Nlist[i]):
answer[myStack.pop()] = Nlist[i]
myStack.append(i)
while(myStack): # 스택에 남아있던 애는 오큰수가 될 수 있는 수가 없었던 것이므로 -1 저장
answer[myStack.pop()] = -1
for i in range(N):
print(answer[i], end = " ")
3번 - 백준 2164번 / 실버 4
큐
from sys import stdin
from collections import deque
N = int(stdin.readline())
myQueue = deque() # 덱! 양 끝에서 데이터삭제.삽입 가능한 자료구조를 큐로 사용
for i in range(1,N+1):
myQueue.append(i) # 추가 append
while(len(myQueue) > 1):
myQueue.popleft() # 큐 빼는 거 popleft
myQueue.append(myQueue.popleft()) #빼는 동시에 값 나옴
print(myQueue[0])
4번 - 백준 11286번 / 실버 1
큐
절댓값 크기 순( 단 같을 시 음수 우선)으로 정렬
from sys import stdin
from queue import PriorityQueue # 큐 / 우선순위 큐 - 넣을 때 put 뺄 때 get
N = int(stdin.readline())
myQueue = PriorityQueue()
for i in range(N):
num = int(stdin.readline())
if (num == 0):
if(myQueue.empty()): # 큐가 비어있으면 True 반환. full은 반대
print("0")
else:
result = myQueue.get() # 뽑고 삭제까지
print(result[1])
else:
myQueue.put((abs(num),num)) # put(우선순위,값)으로 우선순위 할당 가능 / abs()절댓값
스택 큐 덱 헷갈리지 말기
스택 : 후입선출
큐 : 선입선출
덱 : 양쪽에서 삭제.삽입 둘 다 가능
큐 모듈 있는데 덱 모듈 쓰는 차이가 뭐지?
'📊 Algorithm > Algorithm 주제별 정리' 카테고리의 다른 글
🧚♂️알고리즘🧚♂️ - 정렬 - 버블정렬 (0) | 2022.12.27 |
---|---|
🧚♂️알고리즘🧚♂️ - 자료구조 - 투 포인터 / 슬라이딩 윈도우 (0) | 2022.12.25 |
🧚♂️알고리즘🧚♂️ - 그리디 - 그리디 (2) | 2022.11.07 |
🧚♂️알고리즘🧚♂️ - 자료구조 - 배열/리스트/구간합 (0) | 2022.09.27 |
🧚♂️알고리즘 공부🧚♂️ (2) | 2022.09.26 |