알고리즘 자료구조 - 4

4장
 - 스택, 큐

1)
스택
 - 데이터를 일시적으로 저장하기 위해 사용하는 자료구조
 - 후입선출(LIFO, Last In First Out) 방식
 - 스택에 데이터를 저장하는 행위를 push, 데이터를 꺼내는 행위를 pop라고 한다
 - 스택이 가득 차는 위치를 top, 스택의 바닥이 bottom

스택 구조
 - 구조체
    : 스택 용량, 스택 포인터, 스택을 가리키는 포인터
    ** 스택의 크기 == 배열의 요소개수
    ** 스택포인터 : 데이터가 저장되어 있는 바로 다음요소를 가리키고 있다
 - 함수
    : init, push, pop, peek, clear, size, capacity, checkempty, checkfull, search, terminate
    ** Peek(피크): 스택 꼭대기의 데이터를 확인하는 함수, 즉, 스택에서 바로 꺼낼 수 있는 데이터를 확인하는 함수
    ** clear: 스택 데이터를 초기화, 실제로 초기화할 필요는 없고 스택포인터를 초기화하면 된다
    ** terminate: 스택메모리를 free
    ** size: 스택에 쌓여있는 데이터 크기를 반환(정확히는 데이터 수, 즉, 요소 수를 반환)
    ** capacity: 스택의 최대 크기를 반환


2)
큐
 - 데이터를 일시적으로 저장하기 위해 사용하는 자료구조
 - 선입선출(FIFO, First In First Out) 방식
 - 큐에 데이터를 저장하는 행위를 인큐(enqueue), 데이터를 꺼내는 행위를 디큐(dequeue)라고 한다
 - 큐에 데이터가 저장된 맨 처음요소의 인덱스(데이터를 꺼내는 위치)를 front, 데이터를 저장하는 부분(맨 끝 요소 다음 요소의 인덱스)을 rear라고한다


큐 구조
 - 큐 구조는 일반 배열, 링버퍼 등의 형태로 구현이 가능하다
 ** 링버퍼 구조는 오래된 데이터를 버리는 용도로 사용이 가능하며, 링버퍼를 사용하는 큐를 원형큐라고 한다
 ** 시간 복잡도의 경우, 일반 배열은 O(n), 링버퍼는 O(1)이다

 - 구조체
    : 큐 최대 크기, 현재 저장된 요소수, front, rear, 큐 자체를 가리키는 포인터
** 원형 큐에서 데이터가 다 찼을 때 front, rear이 같게되는데, 큐가 비어있는 상태와 동일하여 구분이 불가하다.
   이때 '현재 저장된 요소수' 변수의 값이 max면 데이터가 다 찼다는 것을 알 수 있다

 - 함수
    : init, enque, deque, peek, clear, capacity, size, checkempty, checkfull, search, terminate
    ** 원형 큐에서 enque, deque 함수 구성 시 원형큐가 순환할 수 있도록, enque에서는 rear이 max, deque에서는 front가 max일때 배열의 첫번째 요소로 이동하도록 구성해야한다
    ** search함수 구현 시, 검색의 시작점은 배열의 첫번째 요소가 아닌 큐의 첫요소(front)부터 검색해야 한다