CS - 자료구조(Stack, Queue, Hash Table, Set)

큐 (Queue)

큐는 FIFO(First in First out; 선입 선출)의 특징을 가지는 자료구조. 먼저 들어간 데이터가 먼저 나오는 구조. 대표적으로 스케쥴링에 쓰인다. 먼저 들어온 작업을 먼저 처리하도록 하는 것.

 

 

함수

1. enqueue() (자바의 경우 add()) : 한쪽 방향으로 데이터를 넣는다.
2. dequeue() (자바의 경우 poll()) : 다른쪽 방향으로 데이터를 뺀다. (여기서 dequeue는 덱(deque)과 다르다. deque는 double-ended queue를 줄인거고, dequeue는 de-(접두어) + queue이다.)
3. peek() : dequeue로 빠질 데이터를, 큐에서 제거하진 않고 데이터만 확인한다.
4. isEmpty() : 큐가 비었는지 확인
5. size() : 큐에 들어있는 데이터 갯수

---

스택 (Stack)

스택은 LIFO(Last in First out; 후입 선출)의 특징을 가지는 자료구조. 나중에 들어간 데이터가 먼저 나오는 구조

 

함수

1. push() : 스택에 데이터를 넣습니다.
2. pop() : 스택에서 데이터를 뺍니다.
3. peek() : 스택에서 데이터를 빼진 않고, 가장 위에 있는 데이터만 확인합니다.
4. isEmpty()
5. size()

---

덱 (Deque = Double-ended Queue)

Double-ended Queue라는 의미로, 양쪽으로 넣고 뺄 수 있는 큐. 당연히 양쪽으로 넣고 뺄 수 있는 스택으로도 쓸 수 있고, 한쪽은 스택 한쪽은 큐로 쓸 수 있음. 좀 더 유연한 스택, 큐.

 

함수

1. addFirst() : 덱의 한쪽에 데이터 추가
2. pollFirst() : 덱의 한쪽에서 데이터 빼기
3. peekFirst() : 덱의 한쪽에서 데이터를 빼진 않고 확인만 하기
4. addLast() : 덱의 다른쪽에 데이터 추가
5. pollLast() : 덱의 다른쪽에서 데이터 빼기
6. peekLast() : 덱의 다른쪽에서 데이터를 빼진 않고 확인만 하기
7. isEmpty()
8. size()

---

Hash Table

해시 테이블(맵)은 키와 값의 쌍을 저장하는 자료구조. 해시 테이블은 키를 사용하여 데이터를 빠르게 탐색 가능.

적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 사용.

하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능

하지만, 해시 테이블은 데이터가 많아지면 성능이 저하될 가능성 존재.

• key: value로 저장하는 데이터 구조
• 키를 통해 바로 데이터를 받아올 수 있어 속도가 획기적으로 빨라짐
• 해쉬 : 임의 값을 고정 길이로 변환하는것
• 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해쉬 함수 : 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값 / 해쉬 주소 : 키를 해싱 함수로 연산해서 해쉬 값을 알아내고 이를 기반으로 해뷔 테이블에서 해당 키에 대한 데이터 위치를 일관성있게 찾을 수 잇음
• 슬롯 : 한 개의 데이터를 저장할 수 있는 공간

해시(Hash)

데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것. 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑.

Lee → 해싱함수 → 5 Kim → 해싱함수 → 3 Park → 해싱함수 → 2 ... Chun → 해싱함수 → 5 // Lee와 해싱값 충돌

 

결국 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 'collision' 현상 발생

collision(충돌) 문제 해결

1. 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)
2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장)
3. 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
4. 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함

---

Set

특징

• 데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조
• 중복과 순서 X
• 삽입순서대로 저장되지 않는다. 즉 특정한 순서를 기대할 수 없는 자료구조.
• 수정 가능(mutable)
• Set이라는 인터페이스를 통해 자바에서는 3가지의 Set이 존재.
• 일반적으로 HashSet, TreeSet, LinkedHashSet 순으로 빠르다.
  1. Hash 알고리즘을 이용한 HashSet
  2. 이진 탐색 트리를 사용하여 오름차순 정렬까지 해주는 TreeSet
  3. Set에 순서를 부여해주는 LinkedHashSet