출처 : https://www.youtube.com/watch?v=Q2Up3PN0-nM (코딩알려주는누나)

1. 스택(Stack)

• 선입후출
• 처음에 넣은 것이 가장 바닥에 쌓여있다.

삽입(push)
삭제(pop)
제일 위에 있는 것 확인(peek)

실제 예제

• 함수 호출(콜스택이라고하는데, 콜스택.. ? 스택? 이 적용되어있다)

  함수
   함수
   main

  이렇게 함수가 쌓여있을 때 return 될 때는 맨위에 쌓인 함수의 return 값부터 출력된다.
  
  

• 웹사이트 방문 기록

• 계산기

• stack overflow(stack 에 함수가 넘치게 쌓이면 stackoverflow 에러가 뜬다)

  stack 코드를 짜는 것 해보기

  
  

2. 큐 Queue

• 사람들이 줄 서 있는 모습 FIFO
• 먼저 들어오면 먼저 나간다.
• EnQueue / DeQueue
• Front(가장 먼저들어온 item = 곧 나갈 item) / Rear(가장 나중에 들어온 item)
  - Front와 Rear가 만났다? Empty 상태!

실제 예제

• 자바스크립트 이벤트 루프
• 티켓 판매 사이트 ( 가장 먼저 접속한 사람이 티켓 구매 먼저 한다)

  queue 코드를 짜는 것 해보기

3. 연결리스트

배열

• 배열은 연속적으로 메모리 공간을 차지하게 된다.
• 단점은, 배열은 크기가 정해져있어서 공간을 늘릴 수 없다.
• 자투리 메모리가 생긴다.
• 인덱스를 통해서 접근이 용이하다

연결리스트

• 배열의 단점을 보완한 것
• 메모리에서 연속해서 존재할 필요가 없다.
• 포인터로 연결 정보를 저장한다.
• 노드 [data, pointer] : 데이터와 포인터정보가 같이 저장되어있다.(메모리 사용이 높다)
• 포인터가 한방향으로만 간다? 단순 연결 리스트
• 포인터가 왔다갔다 양방향으로 간다? 이중 연결 리스트
• 배열보다 삽입/삭제 속도가 빠르다.
• 노드로 접근하기 때문에 순차 접근한다.(인덱스 없음)

실제 예제

• 실시간으로 배열이 변할 때
  
  

4. 해시테이블 Hashtable

• 선형으로 된 자료 구조들은 데이터가 커질 수록 속도가 느려진다는 단점을 가지고 있어서 해시 테이블이 이것을 보완하는데,
• 해시테이블은 {키 : 값} 을 가지는 map 구조를 가진다.
• 키 ->(해시함수) ->해시값을 가지는데, 해시 값에 키와 값을 저장하게 된다.
• 무한한 데이터를 유한한 테이블에 넣어준다. 그런데 해시테이블이 꽉차게 된다면? 충돌 발생 !
• 충돌을 해결하기 위한 방법
  - 1. 체이닝 : 같은 인덱스에 두개 이상의 data를 넣어준다.(연결리스트로 추가하는 방식)
  • 2. open addressing : 같은 인덱스를 배정받으면, 비어있는 공간을 찾아서 data를 넣는 방식( 찾을 때는 처음에 배정 받은 인덱스를 찾고, 원하는 data가 없으면 인덱스를 기준으로 하나씩 찾아간다.)

실제 예제

• 지문 등록