[python] 리스트로 구현하는 스택과 큐

스택(Stack)이란?

• 삽입과 삭제가 리스트의 한쪽 끝에서만 이루어지는 선형 자료 구조이다.
• 후입 선출(Last-In First-Out, LIFO) 원칙에 따라 유지된다.
• 사용 빈도가 매우 높은 자료구조이며 함수의 재귀호출을 대신할 수 있다.
• 프링글스를 꺼내먹을 때를 생각해보면 이해가 쉽다.

stack = []

stack.append(1)	# stack = [1]
stack.append(2)	# stack = [1, 2]
stack.append(3)	# stack = [1, 2, 3]

stack.pop()	# stack = [1, 2]
stack.pop()	# stack = [1]
stack.pop()	# stack = []

 

큐(Queue)란?

• 한쪽 끝에서는 삭제, 다른 한쪽 끝에서는 삽입이 이루어지는 자료 구조이다.
• 선입 선출(First-In First-Out, FIFO) 원칙에 따라 유지된다.
• 흔히 은행 업무를 볼 때 사용하는 번호표가 큐의 형태를 띈다.

queue = []

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

queue.pop(0)	# queue = [2, 3]
queue.pop(0)	# queue = [3]
queue.pop(0)	# queue = []