1. 스택(Stack)
LIFO(Last in first out) 후입선출
메소드
-[삭제 연산] pop : 맨 위의 원소 제거
-[삽입 연산] push : 맨 위에 원소 하나 추가
특징
-삽입과 제거가 맨 위(Top)에서만 일어남[삽입/삭제의 시간 복잡도 Θ(1)]
장점
-배열처럼 원소를 삭제하거나 이동했을 때 나머지 원소들이 움직일 필요가 없다.
-데이터를 추가/삭제하는 시간이 짧다.
-맨 위의 원소만 접근 가능
사용 사례
-재귀 알고리즘 : 데이터를 스택에 쌓아두고 재귀가 끝나고 빠져나올 때 순서대로 데이터를 꺼낸다.
-후위 표기법 계산
2. 큐(Queue)
FIFO(First in first out) 선입선출
메소드
-[삭제 연산] dnQueue(디큐): 맨 앞의 원소 제거
-[삽입 연산] enQueue(인큐): 맨 뒤에 원소 하나 추가
특징
-삽입 : 맨 뒤(Rear) / 삭제 : 맨 앞(Front)
-맨 앞과 맨 뒤의 원소만 접근 가능
장점
-데이터 접근, 삽입, 삭제가 빠르다.
사용 사례
-너비 우선 탐색(BFS) 알고리즘
-캐시 구현
문제
스택
https://www.acmicpc.net/problem/9012
stack = list() # 빈 리스트로 스택
VPS = ""
for i in range(int(input())):
stack = list() # 초기화
VPS = "YES" # 올바른 괄호 문자열인가?
for l in input():
if len(stack) == 0: # isEmpty
if l == ")":
VPS = "NO"
break
else:
stack.append(l)
else:
if l == ")": # 만약 닫는 괄호라면
stack.pop(-1) # 마지막 여는 괄호 삭제
else:
stack.append(l) # 여는 괄호라면 추가
if len(stack) != 0:
VPS = "NO" # 남아있는 괄호가 있으면 잘못된 문자열
print(VPS)
https://www.acmicpc.net/problem/10773
stack = list()
for i in range(int(input())):
number = int(input())
if number == 0:
if len(stack) > 0:
stack.pop(-1)
else:
stack.append(number)
stackSum = 0
for i in stack:
stackSum += i
print(stackSum)
뭔가 타임아웃 될 것 같았는데 의외로? 안 됐다?
큐
https://www.acmicpc.net/problem/10845
import sys
input = sys.stdin.readline
print = sys.stdout.write
que = list()
for i in range(int(input())):
ins = input().rstrip()
if ins.startswith("push"):
ins1, ins2 = ins.split()
que.append(ins2)
elif ins == "pop":
if len(que) == 0:
print("%d\n" % -1)
else:
print("%s\n" % que.pop(0))
elif ins == "size":
print("%s\n" % len(que))
elif ins == "empty":
if len(que) == 0:
print("%d\n" % 1)
else:
print("%d\n" % 0)
elif ins == "front":
if len(que) == 0:
print("%d\n" % -1)
else:
print("%s\n" % que[0])
elif ins == "back":
if len(que) == 0:
print("%d\n" % -1)
else:
print("%s\n" % que[-1])
뭔가 한 번은 그냥 풀어보고 그 다음에 제대로 풀어야지~ 했는데 어째 이걸로도 풀려질 것 같아서(큐를 구현하려고 했었다 사실) 빠른 입출력을 적용해보았다... 그러니 이게되네
https://www.acmicpc.net/problem/2164
from collections import deque
que = deque(list(range(1, int(input())+1)))
while(1):
if len(que) == 1:
break
else:
que.popleft()
que.append(que.popleft())
print(que[0])
collections 모듈을 사용해봤다.
참고자료
https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html
https://yoongrammer.tistory.com/45
https://cocoon1787.tistory.com/691
'2022 스터디' 카테고리의 다른 글
[web hacking] 2022 (0) | 2023.11.03 |
---|---|
java 스터디 사전조사 (0) | 2023.05.14 |
넘파이 스터디 20230308 (0) | 2023.03.08 |
JAVA 스윙 공부 (0) | 2022.11.10 |
js 스터디 - 2주차 (0) | 2022.04.15 |