데이터 구조 6 (Queue , pointer)

• Recursion

- 자기 자신(Function body)을 Call 하는 것

- 반복이긴 하지만 for나 while이 아닌 call and return방식으로 반복

- 구성 요소 : Base case ( n==0 or n==1 일 때, ~~) + General Case

- 접근법 : 어느 단계의 값(n)은 한 단계 이전의 결과값(n-1)에서 어떤 차이가 있는지 분석하여 만든다.

 

 

Queues

→ First In, First Out

- 연산: Insert , Delete(하나 꺼낸다 라는 표현이 더 맞음)

           Create Queues (array)

           Full , Empty

 

1) Create 

- Data 형식 - Array

- Front 랑 rear 설정 -> Insert 후, rear++  / Delete 후 Front++

**## 끝에 도착하면 못쓰는 = 형태의 스택이 아니라 동그랗게 구상해야 함.( 안 그러면 한 번만 쓰고 못 쓰는 큐가 되어버림)

이거보단

이렇게 만든다고 구상해야한다.

이렇게 하려면 

- front와 rear 값 증가 시, 끝 원소 후 첫 원소로 이어지도록 구현해야 한다. 

       → rear=(rear+1)%SIZE

      → front=(front+1)%SIZE

 

 

2) empty , full 연산자 

   empty   →    If(front==rear)    /    full       →   (front==rear)

 

문제점 : front==rear인 상황에서 더하려고 하면 꽉 찼다고 안 되고, 빼려고 하면 비었다고 안 됨

 

해결법 :  1칸을 안 쓰는 칸으로 만들어버린다.

 

 empty는 그대로 front==rear일 때로 하고

 full 연산자는(((rear+1)%SIZE) ==front) 일 때, 즉 rear에서 한 칸 더 갔을 때 front 일 때 (rear가 뒤에 있어야 함)

 

---

 

• Pointer

ex) *p=나: /   print(p) = 내 집 주소   / print(*p) = 나 (집에 사는 사람 = p라는 주소에 사는 사람) 

 

 

   → 주소 값 을 다루는 data type

   → NULL을 가리키면, 아무것도 가리키지 않는다 라는 뜻

   → Scope 외에서 다루고 싶을 땐,   주소를 넘겨주고 pointer로 받으면 가능하다.

   → C에서는 malloc,free   / C++ 에서는 a=new int[n]; / delete [a];

     C++에서도 malloc,free 쓸 수 있긴 함.

 

ex)

x=3;  

함수 (x)  →  함수 (int a){ ~~~~a++;}

→  x=? > 3임

 

이유: 함수 call을 하면 전달하는 변수가 직접 가는 게 아니라

                 parameter로 복사해서 함수 내의 로컬변수로 사용하기 때문!

 

 

 

뜬금없는 팁) 

C++에서 C라이브러리 쓸 생각이면

→ 뒤에 있는 h 없애고 앞에 C 붙이기

ex) <string.h>  →  <cstring>

 C라이브러리  →  C++

 

 

출처 : 한동대학교 김호준교수님 - 데이터 구조 PPT