머지소트,스택,큐,연결리스트

merge sort 구현,

merge sort 스택프레임 ( 노트)

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

스택, 큐

ADT : abstract data type 추상자료형

->자료 구조의 인터페이스(함수 시그니처를) (오퍼레이션)을 명시해놓은것 -> 기능명세

요약)어떤 자료구조의 함수 사용법

->구체적인 구현 설명이 들어가면 안된다!

기능과 구현의 구분 : 추상화!

존재하는 자료구조를 가지고 어떤 자료구조를 만들떄 ( 어댑터 패턴 이라고 한다)

1.배열, 2연결리스트 3 파이썬의 리스트 -> 연결리스트로 구현

STACK - LIFO 후입선출, 선입후출

후위표기법 계산기

미로찾기

이 두가지가, 자료구조 공부를 했는가 안했는가의 판단 기준

STACK의 ADT

1. S.empty() -> Boolean 스택이 비어있으면 True, 아니면 False

2. 1. S.push(data) -> None 스택의 맨 위에 데이터를 쌓는다

   2. S.pop()->data 스택 맨 위의 데이터를 삭제하면서 반환

   3. S.peek()->data 스택 맨 위 데이터를 반환

   qeueu

   stack 두개로 qeueu 구현하기

   ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

   연결리스트 (linked list)

   싱글 링크드 리스트

   ㅡ단방향 ( 이전으로 돌아갈 수 없어서 , 처음으로 돌아가야됨) 링크 한개

   더미더블 링크드 리스트 = 이중 연결 링크드 리스트(이거 만들예정)

   ㅡ양방향(왔다 갔다 가능)

링크드 리스트의 최대 약점은 서치 O(n) vs 배열은 arr[idx]