-
[자료구조] 스택(Stack)과 큐(Queue)Computer Science/자료구조 & 알고리즘 2020. 10. 20. 16:18
# 스택(Stack)
스택 자료구조는 상자 쌓기와 비슷하다. 차곡 차곡 아래서부터 위로 상자를 쌓아 나가면, 상자를 뺄 때는 상자들이 무너지지않게 맨 위의 가장 나중에 쌓은 상자부터 빼야 한다. 스택도 마찬가지다. 가장 나중에 들어온 데이터를 가장 먼저 빼는 후입선출(LIFO: Last In First Out) 구조를 가진다.
<상자 쌓기 게임 Dropping Box> 파이썬에서는 별도의 라이브러리 없이 기본 리스트 자료형으로 스택을 쉽게 구현할 수 있다.
# Stack으로 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() 구현 stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() # 가장 윗 부분부터 출력 print(stack[::-1])
# 큐(Queue)
큐는 우리에게 상당히 익숙한 자료구조다. 흔히 얘기하는 선착순 혹은 놀이공원 대기줄처럼 먼저 도착한 데이터가 먼저 그 대기줄을 빠져나가게 된다. 이러한 구조를 선입선출(FIFO: First In First Out) 구조라고 한다. 이러한 큐는 구조적 속성상 '공정한 자료구조'라고도 불린다.
<흔한 놀이공원의 대기 줄.jpg> 큐를 파이썬으로 구현할 때는 collections 라이브러리의 deque 자료구조가 유용하다. 리스트 자료형보다 데이터의 삽입 및 삭제가 빨라 구현이 용이하다.
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() from collections import deque queue = deque() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) queue.popleft() print(queue) # 먼저 들어온 순서대로 출력 queue.reverse() print(queue) # 역순으로 출력
'Computer Science > 자료구조 & 알고리즘' 카테고리의 다른 글
[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap) (0) 2020.11.23 [알고리즘] 이진 탐색 (0) 2020.11.18 [알고리즘] 정렬 알고리즘 (0) 2020.11.17 [알고리즘] DFS(Depth-First Search) & BFS(Breadth-First Search) (0) 2020.10.20 [알고리즘] 재귀 함수(Recursive Function) (0) 2020.10.20