🧚‍♂️알고리즘🧚‍♂️ - 자료구조 - 스택.큐.덱

⭐️ 스택 / 큐 / 덱⭐️

자료구조의 일종

 

스택 - 후입선출(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 모듈

스택/큐로 사용 가능!

[파이썬 기초] 스택과 큐의 기능을 한번에 deque

---

1번 - 백준 1874번 / 실버 3

스택

1874번: 스택 수열

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

스택

17298번: 오큰수

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

큐

2164번: 카드2

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

큐

11286번: 절댓값 힙

절댓값 크기 순( 단 같을 시 음수 우선)으로 정렬

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()절댓값

Edoc2

---

스택 큐 덱 헷갈리지 말기

스택 : 후입선출

큐 : 선입선출

덱 : 양쪽에서 삭제.삽입 둘 다 가능

 

큐  모듈 있는데 덱 모듈 쓰는 차이가 뭐지?