자료구조란 ?

컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.
자세히는 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 의미한다.

배열이란 ? (Array)

연관된 데이터를 모아서 관리하기 위해 사용되는 데이터타입.
변수는 하나의 데이터를 저장하기 위한것이면 배열은 여러 개의 데이터를 저장하기 위한것이다.

배열의 장점

• 인덱스를 사용하여 배열 요소에 빠르게 접근할 수 있다. 시간 복잡도는 O(1)
• 배열은 사용하기 쉽고메모리 관리를 효율적으로 할 수 있다.

배열의 단점

• 배열의 크기가 한 번 정해지면 변경할 수없다.
• 중간에 요소를 삽입하거나 삭제하려면 나머지 요소들을 모두 이동시켜야한다. 시간복잡도는 O(n)

연결리스트란 ? (Linked List)

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
데이터를 담고 있는 노드들이 연결되어 있을 때 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

연결리스트의 장점

• 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다.
• 필요할때만 삽입과 삭제를 할 수 있기 때문에 배열처럼 최대원소 개수 지정이 필요없다.

연결리스트의 단점

• 배열이나 트리 구조와는 다르게 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸린다.
• 구현이 어렵다.

연결리스트의 종류

1. 단일 연결 리스트

• 단일 연결 리스트는 각노드에 자료 공간과 한 개의 포인터 공간이 있고 각 노드의 포인터는 다음 노드를 가리킨다.

2. 이중 연결 리스트

• 이중 연결 리스트의 구조는 단일 연결 리스트와비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

3. 원형 연결 리스트

• 원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜원형으로 만든 구조이다.

스택이란? (Stack)

제한적으로 접근할수 있는 나열 구조.
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 및 후입선출 (Last In First Out)구조이다.
자료를 넣을 때 밀어 넣는다 하여 Push
자료를 꺼내는 작업은 Pop 이라고 한다.

스택의 사용 사례

• 컴퓨터 프로그램에서 함수 호출을 추적할 때, 호출 스택이 사용된다.
• 브라우저에서 뒤로 가기 버튼을 누르면 이전에 방문했던 페이지로 돌아가는 것도 스택 구조이다.

스택의 장점

• 후입선출 구조로, 마지막에 추가된 항목을 쉽게 제거 가능
• 단순한 구조로 쉽고 메모리를 효율적으로 관리 가능

스택의 단점

• 중간 요소 접근이 불가능해서 원하는 데이터 찾으려면 pop을 하며 찾아야됨.
• 크기가 고정된 경우, 초과 데이터를 처리할 수 없다.

큐란? (Queue)

먼저 넣은 데이터가 먼저 나오는 선입선출 (First In First Out)구조로 저장하는 형식이다.
영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하고 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황이라고 생각하면됨.

용어

1. put(insert) : 큐에 자료에 넣는 것
2. get(delete) : 큐에서 자룔르 꺼내는 것
3. front(head) : 데이터를 get할 수 있는 위치
4. rear(tail) : 데이터를 put할 수 있는 위치
5. overflow : 큐가 꽉 차서 자료를 넣을 수 없는 경우
6. underflow : 큐가 비어있어서 자료를 꺼낼 수 없는 경우

큐의 종류

• 선형 큐
  • 막대 모양으로 된 큐
  • 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 한칸씩 옮겨야 하는 단점이 있다.
• 환형 큐 (원형 큐)
  • 선형 큐의 문제점을 보완한 것이 환형 큐이다. front가 큐의 끝에닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식.
• 연결 리스트로 구현한 큐 (링크드 큐)
  • 연결 리스트를 사용한 큐로 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않음.
  • 필요에 따라 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않는다.

큐의 사용 사례

1. 프로세스 스케줄링
   • 운영체제에서 여러 작업을 처리할 때, 작업들이 큐에 저장되어 순차적으로 처리.
2. 네트워크 데이터 처리
   • 네트워크 패킷을 처리할 때, 패킷이 큐에저장되어 순서대로 전송되거나 수신된다.