수학과의 개발자 도전기

큐(queue)란?

:선입 선출 구조, 전단으로는 데이터를 내보내고 후단으로는 데이터를 삽입하는 형태인 자료구조.

-큐 삽입: 후단에 노드를 붙여서 새로운 후단을 만든다.

-큐 제거: 전단의 노드를 없애서 전단 뒤에 있는 노드를 새로운 전단으로 만드는 연산.

순환큐(circular queue)란? 

-순환 큐의 구현에서 후단== 실제 후단+1

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

• 공부한 날짜 : 2022.09.13 

링크드리스트

장점: 스택의 용량에 제한을 두지 않아도 됨

단점: 배열과는 달리 인덱스로 노드에 접근할 수 없음.

-> 링크드 리스트로 스택을 구현하려면 노드는 자신의 위에 위치하는 노드에 대한 포인터를 가지고 있어야 한다. 

1. 노드 정의 

2. 링크드리스트 스택 정의 

링크드리스트 스택에는 탑노드(맨 위에)와 헤드 토드(맨 밑에)가 있다. 

3. 함수 선언 

4. 링크드리스트스택_생성 

5.링크드리스트스택_제거 

앞선 배열스택에서는 노드 없애고, 스택 없애는 줄 알았는데

스택의 Null 여부를 확인해서 노드 없애고, 스택 없앤다. 

6. 링크드리스트스택_노드생성

7. 링크드리스트스택_노드제거 

8. 링크드리스트스택_삽입

9. 링크드리스트스택_제거 

10. 링크드리스트스택_탑 노드 

11. 링크드리스트스택_크기 구하기 

12. 링크드리스트스택_비우기 

-스택이란? 

FILO또는 LIFO 구조를 가짐. 요소의 삽입과 삭제가 자료구조의 한쪽 끝에서만 이루어지는 특징을 가진다. 

소프트웨어 분야에서 엄청나게 중요한 역할. 자동 메모리가 스택을 기반으로 동작. 네트워크 프로토콜도 스택을 기반으로 구성되어 있음.

종류

1. 배열을 이용하여  구현

2. 링크드 리스트를 이용해서 구현  

장점: 구현이 간단하다. 

단점: 동적으로 스택의 용량을 조절하기 어렵다. 

원리: 생성 초기 설정된 용량만큼의 노드가 한꺼번에 생성/ 최상위 노드의 위치를 나타내는 변수 이용해서 삽입, 제거 연산 실행 

-구현이 간단한게 장점인 만큼 다른 자료구조에 비해 코드 작성하는데 큰 어려움이 없었음 

1. 노드 정의 

2. 스택 정의 

다른 자료구조와는 다르게 여기에는 용량과 상위 노드 필드가 들어간다. 

3. 함수 선언 

4. 스택 생성 

6번줄에서 용량의 포인터를 노드의 크기로 설정.

5. 스택 삭제 

스택은 밥그릇이고, 노드를 밥이라고 생각해도 되나?

그럼 밥을 없애고, 밥그릇을 없앤다는 생각으로 노드먼저 없애고, 그다음 스택을 없앤다. 

6. 스택_노드 삽입 

스택에서 인덱스랑 포인터가 1차이 난다는 것 같은데 맞는지 모르겠다. 

포인터 +1 ==인덱스 인 것 같다. 

포인터는 0부터 시작, 인덱스는 1부터 시작?

7. 스택_노드 제거 

말은 제거인데, 뭔가 이해되기로는 맨 위에 있는 노드를 꺼내는 느낌?(말그대로 pop 하듯이)

8. 스택_탑 

AS_Pop과 같은 구조인 것 같다. 

9. 스택_크기

스택의 인덱스를 반환하면 그것이 곧 스택의 사이즈.

10. 스택_비우기

공부한 날짜: 9월 9일 

-환형 링크드 리스트

: 헤드가 테일을 물고 있는 형태의 링크드 리스트

시작을 알면 끝을 알고, 끝을 알면 시작을 알 수 있다.

테일에 접근하는 비용이 많이 작아져서 DLL_AppendNode()함수의 성능을 획기적으로 개선 시킬 수 있고, 뒤에서부터 노드를 찾아나가는 노드 탐색 루틴 구현 가능. 

-환형 링크드 리스트에서 꼭 알아야 할 부분 

1. 테일은 헤드의 '앞 노드'이다.

2.헤드는 테일의 '뒷 노드'이다. 

-환형 링크드 리스트 구현 

1. 노드 선언 

2.

3.

4.

5.

6.

7.

8.

9.

10.