3/4 출근 전 공부하는 알고리즘 (스택, 큐)

 

스택? = LIFO 구조

 

삽입/삭제의 경우 O(1)을 갖는다(맨위의 값을 삭제/삽입한다고 가정하면)

#Python

s=[]

s.append(123)
s.append(456)
s.append(789)
print("size:", len(s))
while len(s) > 0 :
print(s[-1])
s.pop(-1)

 

 

-1을 pop한다고 하면 맨 뒤의 값 pop한 다는 것임 = pop() 마찬가지

 

스택을 실제로 사용하는 경우? 웹 페이지에서 뒤로 가는 경우

 

큐? = LILO

 

맛집 생각해봐라 맛집 같은 경우 사람들이 줄을 서서 기다리는데 먼저 들어온 사람이 먼저 식당 안으로 들어감 

 

마찬가지로 삽입/삭제의 경우 시간복잡도 O(1)

# Python

from collections import deque
# Queue는 너무 느림 알고리즘에서 쓸필요 X

q = deque() # q의 상위 호완의 자료구조 양방향으로 넣고 빼는 것이 가능하다
q.append(123)
q.append(456)
q.append(789)

print("size:", len(q))
while len(q) > 0:
	print(q.popleft())
    
 # dq.append(123) 뒤쪽으로 값 넣음 , dq.appendleft(456) 앞쪽으로 값 넣음