꼭 필요한 자료구조 기초 - 스택, 큐

📌탐색

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

보통 그래프, 트리 등의 자료구조 안에서 탐색

 

📌탐색 알고리즘

DFS, BFS

이를 이해하기 위해서는 먼저 기본 자료구조인 스택, 큐에 대해 이해해야 함

 

📌오버플로, 언더플로

오버플로: 자료구조에 데이터가 이미 가득 찬 상태에서 삽입 연산을 할 때 발생

언더플로: 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 할 때 발생

 

📌스택

박스 쌓기처럼 아래에서부터 위로 차곡차곡 쌓는 구조

선입후출(First In Last Out) , 후입선출(Last In First Out) 구조

 

파이썬에서 스택을 이용할 때 별도의 라이브러리 사용할 필요 없음

기본 리스트에서 append()와 pop() 메서드 사용

 

append(): 리스트의 가장 뒤쪽에 데이터 삽입

pop(): 리스트의 가장 뒤쪽에서 데이터 꺼냄

 

 

📌스택 예제

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) #최하단 원소부터 출력
print(stack[::-1]) #최상단 원소부터 출력

 

📌큐

놀이공원 대기 줄처럼 먼저 온 사람이 먼저 들어가는 구조

선입선출(First In First Out)

 

파이썬에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조 활용

deque는 스택과 큐의 장점을 모두 채택

데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적, queue 라이브러리 이용하는 것보다 더 간단

 

 

📌큐 예제

from collections import deque

# 큐 구현을 위해 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)  # 나중에 들어온 원소부터 출력

 

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬