[Data structure] 스택(Stack), 큐(Queue)

스택(Stack)

• stack : 쌓다
• Last In First Out (LIFO) - 후입 선출 (== First In Last Out, 선입 후출)
• push : 가장 마지막에 쌓는다
• pop : 가장 마지막에 들어간 것을 뺀다

 

python 구현

 - push : append()를 사용하여 수행 (시간복잡도 == O(1))

 - pop : pop()을 사용하여 수행 (시간복잡도 == O(1))

arr = [1,2,3,4]

arr.append(5) #arr에 5를 push
print(arr) #output : [1,2,3,4,5]

arr.pop() #arr의 마지막 원소를 pop
print(arr) #output : [1,2,3,4]

 

큐 (Queue)

• queue : 줄
• First In First Out (FIFO) - 선입 선출 (== Last In Last Out, 후입 후출)
• push : 가장 마지막에 쌓는다
• pop : 가장 먼저 들어간 것을 뺀다

 

python 구현

 ***pop(0)을 사용하여 pop : 시간 복잡도 O(n) (첫 요소를 뺀 후 인덱스 다시 부여해야함) ->collections의 deque를 사용

 - from collections import deque

 - push : append()를 사용하여 수행 (시간복잡도 == O(1))

 - pop : deque.popleft()를 사용하여 수행  (시간복잡도 == O(1))

from collections import deque

arr = deque([1,2,3,4])

arr.append(5) #arr에 5를 push
print(arr) #output : deque([1, 2, 3, 4, 5])

arr.popleft() #arr의 가장 처음 원소 pop
print(arr) #output : deque([2, 3, 4, 5])