자료구조 : 개념 :: 선형 자료구조 : 리스트/스택/큐/덱

선형 자료구조인 리스트, 스택, 큐, 덱은
각각 자료의 접근위치가 다르다

---

리스트

순서와 위치를 가지는 항목들의 모임, 가장 자유로운 선형 자료구조
(!= 집합 : 순서가없음 )

접근 위치

리스트는 임의의 위치(인덱스)에서도 삽입/삭제 가 가능하다.

구현 방법

• 배열 구조 : array
  • 구현이 간단하다
  • 접근 복잡도 : O(1) : 낮은편
  • 삽입/삭제 시 비효율 : 오버헤드 발생
  • 크기에 제한이 있음
  
  
• 연결된 구조 : Linked list
  • 구현이 복잡
  • 접근 복잡도 : O(n)
  • 삽입/삭제 효율적
  • 크기에 제한이 없음

파이썬 리스트

파이썬 리스트는 스마트한 동적 array로 구현
: 필요한 양보다 넉넉한 크기의 메모리 사용

동적 배열 구조는 용량 증가 시 새로운 배열을 생성하여 기존 배열에 복사하고,
기존 배열을 해제한다.

• 파이썬 연산 복잡도
  • append(e) : 대부분 O(1)
    -> 맨 앞에 새로운 항목을 삽입할 땐, 먼저 모든 항목을 한칸씩 뒤로 이동해야 하기 때문에
  • insert(pos, e) : O(n)
  • pop(pos) : O(n)

---

스택

쌓는 더미로, 후입선출(LIFO: Last-In First-Out)의 특징,
위에서 들어와서 위로 나간다.

주요 연산

• push(e) : 맨위에 삽입
• pop(): 맨 위 항목 꺼내서 반환

파이썬 배열로 구현 시

삽입/삭제는 리스트 맨 뒤가 유리하다.
why ? 파이썬 리스트는 뒤에 넣는 것이 자연스러워 O(1)의 연산이 발생하고,
전단에 삽입 시 뒤의 모든 항목을 한칸씩 뒤로 옮기므로 O(n)의 연산이 발생

스택의 용도

• 뒤로가기, 되돌리기
• 함수 호출
• 괄호 검사
• 후위 표기식 계산, 중위 표기식의 후위표기 변환
• DFS : 깊이우선탐색 : 미로찾기

---

큐 (원형큐) : 시계방향 회전

큐는 선입선출 : FIFO (Fisrt-In Fisrt-Out)의 자료구조이다.
위에서 들어와서 아래로 나간다.

접근 위치

삽입은 큐의 후단(rear)에서, 삭제는 큐의 전단(front)에서 이뤄진다.

공백상태 & 포화상태

공백상태 : front == rear
포화상태 : front % M == (rear + 1) % M

주요 연산

• enqueue
• dequeue

BFS : 너비우선탐색

---

덱 (원형큐 상속)

리스트에 이어 선형 자료구조 중 두번째로 입출력이 자유로운 자료구조
반 시계방향 회전이 ㅣㅍㄹ요하다

큐는 rear에서만 삽입, front에서만 삭제하지만
덱은 front/rear 양쪽에서 삽입/삭제가 가능하다.

주요 연산

• add_front
• delete_front
• add_rear
• delete_rear
• get_front
• get_rear