스택과 큐

자료구조란?

데이터를 표현하고 관리하고 처리하기 위한 구조

• 삽입 : 데이터를 삽입 (PUSH)
• 삭제 : 데이터를 삭제 (POP)

스택

스택(stack)은 이름 그대로 쌓는걸 생각하면 된다.

블럭을 쌓는 놀이를 한다고 생각해보자 처음엔 차근차근 블럭을 아래에서 위로 쌓을 것이다. 다시 쌓은 블럭을 해체시키려면 위에서부터 하나씩 꺼내야한다. 즉 맨 마지막에 쌓은 블럭을 젤 먼저 뽑는 거다. 이를 선입후출이라고 한다!

스택 예시

stack=[]

stack.append(2)
stack.append(3)
stack.append(1) #stack->[2,3,1]
stack.pop() #stack->[2,3]
stack.pop() #stack->[2]
stack.pop() #stack->[]

 

큐

큐(Queue)는 음식점 대기줄을 생각해보자. 차례대로 온 사람순으로 대기줄에 서서 기다리면 매장에서 자리가 나는대로 처음 온 손님부터 자리에 앉힌다. 큐는 이처럼 먼저 들어온 것을 먼저 내보내기 때문에 공정한 자료구조라고도 한다고 한다. 선입선출구조이다!

queue=[]

queue.append(2)
queue.append(3)
queue.append(1) #queue [2,3,1]

queue.pop(0) #queue->[3,1]
queue.pop(0) #queue->[1]
queue.pop(0) #queue->[]

 

또는 collections 모듈을 사용하여 구현하기도한다.

collections모듈에서 제공하는 deque 자료구조는 스택과 큐의 장점을 둘 다 사용하여 데이터를 넣고 빼는 속도를 리스트보다 효율적으로 높일 수 있다. 

from collections import deque

queue=deque()

queue.append(2)
queue.append(3)
queue.append(1) #deque([2,3,1])

queue.popleft() #deque[(3,1)]

#역순으로 바꾸기
queue.reverse() #deque([1,3])

#deque 객체를 list로 바꾸기
queue=list(queue)