왜 데이터 구조가 중요할까?:
문제마다 적합한 자료형이 필요하다.
프로그램 = 데이터구조 + 알고리즘
데이터 구조 == 데이터 + 구조
문제에 적합한 자료형을 사용할 경우 데이터를 필요에 따라 저장하고 활용할 수 있으므로 문제를 더 효율적으로 풀기 위한 도구가 된다.
즉, 데이터 구조를 학습한다는 것은 어떤 데이터를 어떻게 저장하고 활용할 수 있다는 것을 아는 것이다.
- 시퀀스형(순서가 존재하며 인덱스로 접근이 가능)
-
리스트
-
튜플
-
레인지
- 비시퀀스형(순서가 존재하지 않고 인덱스로 접근이 불가능)
-
세트
-
딕셔너리
스택이란 쌓는다는 의미로써, 마치 접시를 쌓고 빼듯이 데이터를 한쪽에서만 넣고 빼는 자료구조이다.
스택의 자료가 들어가고 나가는 방식은 LIFO(후입선출) 방식이 활용된다.
스택의 자료 조작은 다음의 메서드로 이루어진다.
-
.push(): 스택에 새로운 데이터를 삽입하는 행위 / 시간복잡도: O(1) -
.pop(): 스택의 가장 마지막 데이터를 가져오는 행위 / 시간복잡도: O(1)
넣을 때는 들어간 순서대로 데이터가 쌓이게 되고 뺄 때는 위에서부터 빼게 된다. 즉 마지막으로 들어간 것이 먼저 나오게 된다.
후입선출: 들어온 순서와 반대로 나가는 것이 Stack의 특징이다.
스택은 아래와 같은 상황에서 유용하기에 사용된다.
-
뒤집기, 되돌리기, 되돌아가기
데이터가 반대로 정렬되거나, 뒤집히는 상황이 필요할 때
ex: 브라우저의 뒤로가기 기능,
ctrl+z -
마무리 되지 않은 일을 임시 저장
ex: 괄호 매칭, 함수 호출, 백트래킹, DFS(깊이 우선 탐색)
한 쪽 끝에서 데이터를 넣고, 다른 한 쪽에서만 데이터를 뺄 수 있는 자료구조이다.
스택과는 반대로 가장 먼저 들어온 데이터가 가장 먼저 나가는 FIFO(선입선출) 방식이다.
우리가 일상 생활에서 줄서는 것과 같다고 생각하면 된다.
-
.dequeue(): 큐의 맨 앞 데이터를 가져오는 경우 / 시간복잡도: O(N) (pop()) -
.enqueue(): 큐의 맨 뒤에 데이터를 삽입하는 행위 / 시간복잡도: O(1) (append())
큐 또한 리스트로 나타낼 수 있는데, dequeue는 pop(0)으로, enqueue는 append()로 구현 가능하다.
하지만 pop을 쓸 경우 선형복잡도를 가지기 때문에 비효율적이다. 따라서 Deque(데크)를 쓴다.
Deque에서 pop(0) == popleft()를 할 경우 시간복잡도가 O(1)이기 때문에 훨씬 효율적이다.
양방향 삽입, 제거가 모두 상수 복잡도이기 때문에 매우 좋다! 따라서 Deque를 애용하도록 하자!
데이터의 삽입, 추출이 많은 경우, 시간을 크게 단축시킬 수 있다. 큐와 스택의 성질을 모두 지니는 파이썬에서 제공하는 자료형이다.
다른 말로는 Double Ended Queue라고 불린다.
-
.append(): 덱의 인덱스 -1 위치에 원소를 append한다. 주로 스택 구현 시에 사용된다. -
.popleft(): 덱의 인덱스 0 위치의 원소를 pop한다. 주로 큐 구현 시에 사용된다. -
.appendleft(): 덱의 인덱스 0 위치에 원소를 append한다. -
.pop(): 덱의 인덱스 0 위치에 원소를 pop한다. 주로 스택 구현 시에 사용된다.
# Dequeue 사용 예시
from collections import deque
numbers = [1,2,3,4,5]
queue = deque(numbers)
queue.append(6) # [1,2,3,4,5,6]
queue.popleft() # [2,3,4,5,6]
print(queue) # [2,3,4,5,6]https://velog.io/@sdh7700/%EC%8A%A4%ED%83%9DStack-%ED%81%90Queue-%EB%8D%B0%ED%81%90Double-ended-Queue (Stack, Queue, Deque)
https://gusdnd852.tistory.com/242 (Stack, Queue, Deque)