자료구조의 배열/스택/큐/탐색구조/그래프/트리/해쉬테이블 등 자료 구조 기본개념정리

배열 (Array): 배열은 동일한 자료형의 원소를 일렬로 나열한 자료 구조입니다. 각 원소에는 인덱스라는 고유한 번호가 지정되어 있으며, 이 인덱스를 통해 배열 내의 특정 위치에 있는 원소에 접근할 수 있습니다. 배열은 원소의 개수를 바꿀 수 없으며, 정적 메모리 할당을 사용하므로 크기가 미리 결정되어야 합니다.

https://www.educative.io/answers/what-is-a-3-d-array

 

스택 (Stack): 스택은 후입선출 (LIFO) 원칙을 따르는 자료 구조입니다. 스택에는 push(삽입)과 pop(삭제)이라는 두 가지 기본 연산이 있습니다. 스택에서 가장 최근에 삽입된 원소를 top이라고 하며, top을 통해 스택의 맨 위에 있는 원소에만 접근할 수 있습니다.

스택은 후입선출(Last-In-First-Out, LIFO)의 원칙을 따릅니다. 이는 가장 마지막에 삽입된 원소가 가장 먼저 삭제되는 구조를 말합니다. 스택에서는 새로운 원소가 스택의 맨 위에 삽입되고, 삭제 연산이 수행될 때는 스택의 맨 위에 있는 원소가 삭제됩니다. 이러한 스택의 특징은 간단하면서도 다양한 응용 분야에서 사용됩니다. 예를 들어, 함수 호출 스택에서는 함수 호출 시 지역 변수와 함수 매개변수 등의 정보가 스택에 저장되고, 함수가 반환될 때 스택의 맨 위에 있는 데이터가 먼저 반환됩니다. 스택을 구현하는 방법에는 배열(Array)이나 연결 리스트(Linked List)를 사용하는 등 다양한 방법이 있으며, 스택의 크기를 동적으로 조절하는 동적 스택(Dynamic Stack)을 구현할 수도 있습니다.

 

큐 (Queue): 큐는 선입선출 (FIFO) 원칙을 따르는 자료 구조입니다. 큐에는 enqueue(삽입)와 dequeue(삭제)이라는 두 가지 기본 연산이 있습니다. 큐에서 가장 먼저 삽입된 원소를 front, 가장 나중에 삽입된 원소를 rear라고 하며, front와 rear를 통해 각각 큐의 맨 앞과 맨 뒤에 있는 원소에 접근할 수 있습니다.

큐(Queue)는 선입선출(First-In-First-Out, FIFO)의 원칙을 따릅니다. 이는 가장 먼저 삽입된 원소가 가장 먼저 삭제되는 구조를 말합니다. 큐에서는 새로운 원소가 큐의 맨 뒤에 삽입되고, 삭제 연산이 수행될 때는 큐의 맨 앞에 있는 원소가 삭제됩니다. 이러한 큐의 특징은 다양한 응용 분야에서 사용됩니다. 예를 들어, 운영체제에서는 입출력 버퍼에 대한 작업 처리를 위해 큐를 사용합니다. 또한, 대기열 시스템에서는 일정한 순서대로 처리해야 하는 작업을 큐에 저장하고, 처리 우선순위에 따라 큐에서 처리됩니다.

큐를 구현하는 방법에는 배열(Array)이나 연결 리스트(Linked List)를 사용하는 등 다양한 방법이 있으며, 원형 큐(Circular Queue)를 사용하여 큐의 공간을 최대한 활용할 수 있습니다. 또한, 큐에서는 삽입 연산을 enqueue(큐의 맨 뒤에 원소를 삽입), 삭제 연산을 dequeue(큐의 맨 앞에서 원소를 삭제)이라고 부릅니다. 이때, 큐의 가장 앞쪽을 가리키는 인덱스를 front, 큐의 가장 뒤쪽을 가리키는 인덱스를 rear라고 부릅니다. 큐에서 삭제 연산이 수행될 때는 front 인덱스를 증가시켜 가장 앞쪽의 인덱스를 변경하고, 삽입 연산이 수행될 때는 rear 인덱스를 증가시켜 가장 뒤쪽의 인덱스를 변경합니다.

https://coderworld109.blogspot.com/2017/12/applications-of-queue-data-structure.html

Applications of Queue data structure

탐색 구조 (Search Structure): 탐색 구조는 효율적인 검색과 삽입, 삭제 연산을 지원하는 자료 구조입니다. 대표적으로 이진 검색 트리, 레드-블랙 트리, AVL 트리, B-트리 등이 있습니다.

 

그래프 (Graph): 그래프는 정점(vertex)과 간선(edge)으로 이루어진 자료 구조입니다. 각 정점은 서로 다른 정점과 간선을 통해 연결되어 있으며, 이를 통해 그래프 내의 객체 간의 관계를 표현할 수 있습니다. 그래프는 방향 그래프와 무방향 그래프로 나뉘며, 그래프 내에 사이클이 있는 경우 사이클 그래프, 사이클이 없는 경우 비사이클 그래프(트리)라고 합니다.

https://lunakimvision.blogspot.com/2019/06/data-structure-graph.html

트리 (Tree): 트리는 그래프의 일종으로, 부모-자식 관계를 가지는 계층적인 구조를 갖습니다. 각 노드는 자식 노드를 가질 수 있으며, 부모 노드를 가리키는 포인터와 자식