큐 - 선형

• First In First Out 의 선형구조 (FIFO) - DeQueue(unshift), EnQueue(push)

• Linear Queue, Circular Queue가 존재

  ex. 대기 줄

선형 큐(Linear Queue)

• Array로 표현 가능 - 하지만 DeQueue되어 빈 공간을 없애기 위해 앞으로 배열을 정렬하면 선형 시간이 필요 (낭비)
• Linked List 로 표현하게 되면 index 고민 하지 않아도 됨!
• Array & Linked List

환형 큐(Cirecular Queue)

• 연결 리스트로 구현해도 크게 이점은 없음..
• 범위를 벗어나면 0부터 다시 입력되도록 하기
• 하지만 잘 사용은 안함.
• Array로 구현

해시 테이블 - 선형

• key와 value를 받아 key를 해싱해서 나온 index에 값을 저장하는 선형 자료구조
• 삽입 O(1), key를 알고 있다면 삭제, 탐색 O(1)

해시 함수

• 입력받은 값을 특정 범위 내 숫자로 변경하는 함수

  

해시 테이블의 문제점 - 해시 충돌