자료구조 (Data Structure)
데이터를 표현하고 관리하고 처리하기 위한 구조
자료구조 중 스택과 큐는 자료구조의 기초 개념으로, 다음의 두 핵심적인 함수로 구성된다.
- 삽입(Push) : 데이터를 삽입한다.
- 삭제(Pop) : 데이터를 삭제한다.
스택과 큐를 사용할 때에는 오버플로와 언더플로도 고민해야 한다.
- 오버플로(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생
- 언더플로(Underflow) : 특정한 자료구조에 데이터가전혀 들어있지 않은 상태에서 삭제 연산을 수행할 때 발생
스택 (Stack)
후입선출(Last In First Out) 구조
박스 쌓기에 비유할 수 있다.
예시
삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
의 스택 연산을 파이썬 코드로 표현하면 다음과 같다.
stack = []
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
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]) # 최상단 원소부터 출력실행 결과
파이썬의 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.
큐 (Queue)
선입선출(First In First Out) 구조
대기줄에 비유할 수 있다.
예시
삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
의 큐 연산을 파이썬 코드로 표현하면 다음과 같다.
from collections import deque
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
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) # 나중에 들어온 원소부터 출력실행 결과
파이썬으로 큐를 구현할 때는 list가 아닌 collections 모듈에서 제공하는 deque 자료구조를 활용한다.
📘 이것이 취업을 위한 코딩 테스트다 with 파이썬 :: chapter 05
