[자료구조] Stack & Queue & Map & Set

자료구조란?

• 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.
• 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조(집합)

자료구조를 배우는 이유

✔️ 데이터를 체계적으로 저장하고, 효율적으로 활용하기 위해서 자료구조를 사용한다.

✔️ 대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다.

• 많은 자료구조를 알아두면, 특정 문제를 해결하는 데에 상황에 가장 적합한 자료구조를 빠르게 찾아 데이터를 정리하고 활용하여문제를 빠르고 정확하게 해결할 수 있다.
• 이것은 문제 해결 능력을 필요로하는 알고리즘과 굉장히 밀접한 연관성이 있다.
• 결국 문제해결을 하기 위해서 배운다.

💡 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며, 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있습니다.

1. Stack

• 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO구조 (Last In First Out)
• 모든 원소들의 삽입과 삭제가 한쪽 끝에서만 이루어진다.
• 한쪽 끝에서 이루어지기에 가장 마지막에 입력된 원소가 가장 처음으로 제거된다.
• 즉, 후입선출 (LIFO, Last In First Out)이 이루어진다.
• 웹사이트 방문기록, 실행 취소, 함수 호출 등, 가장 마지막에 실행한 것을 가장 처음으로 가져와야 할 때 사용된다.
• 스택(Stack)은 순차적으로 데이터를 추가하고 삭제하기 때문에 배열 기반인 ArrayList와 같은 컬렉션 클래스가 적합하다.

2. Queue

• 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 구조 (First In First Out)
• 한 쪽 끝에서는 삭제가, 다른 한 쪽에서는 삽입이 일어난다.
• 즉 삭제와 삽입이 되는 구간이 다르기 때문에 가장 먼저 삽입된 원소가 가장 처음 제거된다.
• 즉, 선입선출 (FIFO, First In First Out)이 이루어진다.
• 종류로는 선형 큐와 원형 큐가 있는데, 선형 큐는 정해진 사이즈의 끝에 도달하면 더 이상 추가가 불가능하지만 원형 큐는 가능하다.
• BFS 알고리즘, 대기 번호, 프린터의 출력 처리, 컴퓨터 운영체제의 테스크 스케쥴링(가장 간단한 형태의 선입선 처리 스케쥴링 정책) 등 순서가 중요할 때 사용된다.
• 큐(Queue)는 데이터를 꺼낼 때 항상 첫 번재 저장된 데이터를 삭제하기 때문에 배열기반의 컬렉션보다
• 데이터의추가 삭제가 쉬운 LinkendList가 적합하다.

Circular Queue (원형 큐)

원형 큐

• Ring Buffer라고도 함
• Linear Queue보다 더 나은 이점으로는 메모리 사용률이 좋음
• 활용 예시 : 운영체제 메모리관리, CPU 스케쥴 관리
• 단점 : Saturation(포화) 확인 위해선 공백상태 하나 필요

Circular Queue

JAVA Collection Framework의 상속 기본 구조

Java Collection Framework

3. Map

• Key와 Value의 한쌍으로 이루어지는 데이터의 집합.
• Key에 대한 중복이 없으며 순서를 보장하지 않습니다.
• 뛰어난 검색 속도를 가집니다.
• 인덱스가 따로 존재하지 않기 때문에 iterator를 사용합니다.

Map의 종류와 특징

• HashMap
  • Key에 대한 중복이 없으며 순서를 보장하지 않는다.
  • Key와 Value 값으로 NULL을 허용한다.
  • 동기화가 보장되지 않는다.
  • 검색에 가장 뛰어난 성능을 가진다.
• HashTable
  • 동기화가 보장되어 병렬 프로그래밍이 가능하고 HashMap 보다 처리속도가 느리다.
  • Key와 Value 값으로 NULL을 허용하지 않는다.
• LinkedHashMap
  • 입력된 순서를 보장한다.
• TreeMap
  • 이진 탐색 트리를 기반으로 키와 값을 저장한다.
  • Key 값을 기준으로 오름차순 정렬되고 빠른 검색이 가능하다.
  • 저장 시 정렬을 하기 때문에 시간이 다소 오래 걸린다.

4. Set

• 데이터의 집합이며 순서가 없고 중복된 데이터를 허용하지 않습니다.
• 중복되지 않은 데이터를 구할 때 유용합니다.
• 빠른 검색 속도를 가집니다.
• 인덱스가 따로 존재하지 않기 때문에 iterator를 사용합니다.

Set의 종류와 특징

• HashSet
  • 인스턴스의 해시값을 기준으로 저장하기 때문에 순서를 보장하지 않는다.
  • NULL 값을 허용한다.
  • TreeSet보다 삽입, 삭제가 빠르다.
• LinkedHashSet
  • 입력된 순서를 보장한다.
• TreeSet
  • 이진 탐색 트리를 기반으로 한다.
  • 데이터들이 오름차순으로 정렬된다.
  • 데이터 삽입, 삭제에는 시간이 걸리지만 검색, 정렬이 빠르다.

---

🔗🌐참고 링크

자료 구조 List, Set, Map의 차이 / Set과 Map 비교

[자료구조] 자료구조란? (자료구조를 배우는 이유) - 하나몬

자료구조 : 자료구조란? (Data Structure)

자료 구조란? 데이터 구조란? Data Structure?

[Data Structure] 스택(Stack)과 큐(Queue) 개념, 특징, 활용 예시

05. [자바] Stack, Queue 그리고 Deque - 자료구조

https://123okk2.tistory.com/200

[자료구조] List, Map, Set 특징 정리
Circular Queue Data Structure

Types of Queues

[Programming] Queue: 원형 큐(Circular Queue) 단계별 과정

Circular Queue Data Structure
[자료구조] 큐(Queue)와 원형큐(Circular Queue) 개념과 구현