추상 자료형_1(Python)

리스트

데이터 간 순서 관계를 유지할 수 있다.

파이썬 리스트는 동적 배열 자료구조로 구현되어있다.

접근/ 탐색/ 삽입/ 삭제의 기능을 가지고 있다.

---

큐

데이터간 순서 관계를 유지할 수 있다.

맨 뒤 데이터 추가

맨 앞 데이터 삭제

맨 앞 데이터 접근의 기능 등을 가지고 있다.

FIFO 

First-in-first-out

가장 먼저 들어온 데이터가 가장 먼저 삭제됨을 말한다. (선입선출)

큐는 동적배열과 더블리 링크드 리스트로 구현이 가능하며

파이썬에서는 (deque) 자료형은 더블리 링크드 리스트로 구현되어 있다.

 

일반적으로  queue는 한쪽으로 들어가고 한쪽으로만 나가는데, deque는 양쪽으로 들어가고 양쪽으로 나갈 수 있다.

(스택을 deque로 사용하기도 한다)

파이썬에서는 deque 자료형을 사용해 큐를 사용할 수 있다.

Doubly-ended-queu의 약자 (양면 큐)

맨 앞과 뒤에 데이터를 삽입하고 삭제 할 수 있는 자료형이다.

from collections import deque

A = deque()

---

스택

데이터간 순서를 약속하는 추장 자료형이다.

맨 뒤 데이터 추가

맨 뒤 데이터 삭제 및 접근의 기능 등을 가지고 있다.

LIFO

Last-in-first-out

가장 마지막에 들어온 데이터가 가장 먼저 삭제됨을 말한다. (후입 선출)

스택은 동적 배열과 더블리 링크드 리스트로 구현이 가능하며

파이썬에서는 (deque) 자료형과 리스트 자료형 어느 것을 사용해도 시간 복잡도의 차이가 없다. 

 

파이썬에서는 deque 자료형을 사용해 스택을 사용할 수 있다.

from collections import deque

A = deque()

---

파이썬에서 어떤 자료형을 사용할 건지 잘 고르는 건 결국 어떤 자료 구조를 쓸 건지 고르는 것과 비슷하다.

데이터에 어떤 관계가 필요하고 어떤 기능들을 사용할 건지 잘 생각하면 더 효율적인 프로그램을 쓸 수 있다.

내가 해결하고자 하는 문제를 어떤 자료형으로 해결할지를 판단하기 위해선 추상 자료형 뒤에 가려진 자료구조에 대한 이해가 뒷받침되어 야 할 것이다.

 

출처 : 코드 잇(자료구조)

자료 구조 | 코드잇 (codeit.kr)