수학과의 개발자 도전기

-스택이란? 

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.

공부 날짜: 9월 8일 

-더블 링크드 리스트

: 링크드 리스트의 탐색 기능을 개선한 자료구조.

노드가 자신의 앞,뒤에 있는 노드의 포인터를 가지고 있어 양방향 탐색이 가능함 

-Doubly LinkedList 구현

1. 노드 선언

2.함수 선언

3. 노드 생성

4. 노드 제거 

5. 노드 추가 

6. 노드 삽입 

7. 노드 제거 

이부분은 몇번 더 반복해야할 것 같다. 

8. 노드 탐색 

9. 노드 개수 세기 

2021.09.06

자료구조 공부 시작

책 '뇌를 자극하는 알고리즘'

<공부한 내용>

-리스트,노드,링크드 리스트가 무엇인지에 대해 공부

-노드 생성/소멸/추가

-노드 추가할 때 List의 포인터의 포인터로 파라미터 설정해야하는 이유 공부(몰라서 다음날로 미룸)

-리스트

-노드

-링크드리스트

1. 노드 표현하기

2. 함수 원형 선언(인터페이스 같은 느낌인건가?,,,)

3.  노드 생성 

4. 노드 소멸 

5. 노드 추가

항상 시작할 땐 null인지,head가 remove인지 등 기본적인 거 체크하는 코드 구현하고 넘어가기 

head부터 시작해서 tail을 찾을 때까지 while을 돌린다. tail을 찾으면 그것의 다음 노드를 새 노드로 삽입하면 끝. 

6. 노드 삽입 

추가는 링크드리스트 끝에 새로운 노드를 넣는 건데 삽입은 리스트 중간에 노드를 넣는 걸 의미함(current 노드가 필요)

7. 헤드삽입

8. 노드 제거 

9.  노드 세기