View
자료구조 스택(Stack), 큐(Queue)
스택(Stack)
LIFO(후입선출)
흔히 박스를 쌓는것으로 생각하면 된다
제일 먼저 쌓은 박스는 제일 나중에, 제일 나중에 쌓은 박스가 제일 먼저 나온다
Python 스택 구현 예
num = []
num.append(값) # 보통 append() 로 삽입
num.pop() # pop() 으로 맨 나중에 들어온거(제일 우측) 삭제
print(num[::-1]) # 최상단 즉, 맨 나중에 들어간 원소부터 출력
print(num) # 최하단 즉, 맨 먼저 들어간 원소부터 출력
큐(Queue)
FIFO (선입선출)
에스컬레이터를 생각하면 된다
먼저 탄 사람이 제일 먼저 도착하고, 제일 나중에 탄 사람이 제일 마지막에 도착한다
Python 큐 구현 예
리스트 자료형으로 큐를 기능적으로 구현할수 있지만
시간 복잡도가 더 높아서 비효율적이라 큐를 이용할때는 deque 라이브러리 사용
from collections import deque
num = deque() # 큐 사용할때 deque 라이브러리 사용
num.append(값) # 오른쪽 끝에 삽입
num.appendleft(값) # 왼쪽 끝에 삽입
num.pop() # 오른쪽 끝 엘리먼트를 가져오는 동시에 삭제
num.popleft() # 왼쪽 끝 엘리먼트를 가져오는 동시에 삭제
num.extend(리스트) # 주어진 리스트를 순환하면서 데크의 오른쪽에 추가
num.extendleft(리스트) # 주어진 리스트를 순환하면서 데크의 왼쪽에 추가
num.remove(값) # 값을 데크에서 찾아 삭제
num.rotate(수) # 데크를 수 만큼 회전한다(양수(1)면 오른쪽, 음수(-1)면 왼쪽)
print(num) # 먼저 들어간 원소부터 출력
num.reverse() # 리스트 역순으로 바꾸기
print(num) # reverse() 로 순서가 바뀌어서 나중에 들어온 원소부터 출력
참고자료
반응형
reply