(윤성우의 열혈 자료구조) 6장 /7장

스택의 정의
스택이란 나중에 들어가는 것이 먼저 나오는 구조인 후입
선출 이라는 특성을 가지고 있는 나열 구조 이다.

스택의 ADT
크게 3가지로 나뉘어 볼 수 있다
1. push(넣는다)
2. pop(꺼낸다)
3. peek(들여다 본다)

배열 기반 스택의 구현
헤더파일

#ifndef __AB_STACK_H__
#define __AB_STACK_H__
#define TRUE 1
#define FALSE 0
#define STACK_LEN 100
typedef int Data;
typedef struct _arrayStack // 배열 기반 구조체 정의
{
	Data stackArr[STACK_LEN];
int topIndex;
}ArrayStack;
typedef ArrayStack Stack;
void StackInit(Stack* pstack); // 스택의 초기화 진행
int SIsEmpty(Stack* pstack); // 스택의 빈경우 유무 확인
void SPush(Stack* pstack, Data data); // 스택의 데이터 저장
Data SPop(Stack* pstack); // 스택의 데이터 삭제
Data SPeek(Stack* pstack); // 스택의 저장된 데이터 반환
#endif

#include <stdlib.h>
#include <stdio.h>
#include "ArrayBaseStack.h"
void StackInit(Stack* pstack) {
	pstack->topIndex = -1; //빈 상태
}
int SIsEmpty(Stack* pstack) {
	if (pstack->topIndex == -1)
		return TRUE; // 비어 있다면
	else
		return FALSE; // 비어 있지 않다면
}
void SPush(Stack* pstack, Data data) {
	pstack->topIndex += 1; //데이터 추가 연산
	pstack->stackArr[pstack->topIndex] = data; // 데이터 저장
}
Data SPop(Stack* pstack) {
	int rIdx;
	if (SIsEmpty(pstack)) {
		printf("Stack **텍스트**Memory Error!\n");
		exit(-1);
	}
	rIdx = pstack->topIndex;
	pstack->topIndex -= 1; 
	return pstack->stackArr[rIdx]; // 삭제되는 데이터 반환
}
Data SPeek(Stack* pstack) {
	if (SIsEmpty(pstack)) {
		printf("Stack Memory Error!\n");
		exit(-1);
	}
	return pstack->stackArr[pstack->topIndex]; 맨 위에 저장된 데이터 반황
}

메인함수

#include <stdio.h>
#include "ArrayBaseStack.h"
int main(void) {
	Stack stack;
	StackInit(&stack);
	SPush(&stack, 1); SPush(&stack, 2);
	SPush(&stack, 3); SPush(&stack, 4);
	SPush(&stack, 5);
	while (!SIsEmpty(&stack)) 
		printf("%d ", SPop(&stack));
	return 0;
}

고려 해야 할 점!
pop에는 삭제와 반환의 의미가 같이 들어가 있다. 즉 데이터를 꺼내면 삭제가 되고 그 즉시 반환도 가능하다. 허나 peek은 pop과 달리 꺼내서 확인은 하되 소멸 시키지는 않는 함수 이다. 이 차이 분명히 알길 바란다!

열결 리스트 기반 스택의 구현
헤더파일

#ifndef __LB_STACK_H__
#define __LB_STACK_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node { // 연결 리스트 기반 스택 구조체
	Data data;
	struct _node *next;
} Node;
typedef struct _listStack {
	Node *head;		
} ListStack;
typedef ListStack Stack;
void StackInit(Stack *pstack); 
int SIsEmpty(Stack *pstack);
void SPush(Stack *pstack, Data data);
Data SPop(Stack *pstack);
Data SPeek(Stack *pstack);
#endif

#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"
void StackInit(Stack *pstack) { 
	pstack->head = NULL;
}
int SIsEmpty(Stack *pstack) {
	if(pstack->head == NULL)
		return TRUE;
	else
		return FALSE;
}
void SPush(Stack *pstack, Data data) {
	Node *newNode = (Node *)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = pstack->head;
	pstack->head = newNode;
}
Data SPop(Stack *pstack) {
	Data rdata;
	Node *rnode;
	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!\n");
		exit(-1);
	}
	rnode = pstack->head;
	rdata = pstack->head->data;
	pstack->head = pstack->head->next;
	free(rnode);
	return rdata;
}
Data SPeek(Stack *pstack) {
	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!\n");
		exit(-1);
	}
	return pstack->head->data;
}

메인 함수

#include <stdio.h>
#include "ListBaseStack.h"
int main(void) {
	Stack stack;
	StackInit(&stack);
	SPush(&stack, 1);SPush(&stack, 2);
	SPush(&stack, 3);SPush(&stack, 4);
	SPush(&stack, 5);
	while(!SIsEmpty(&stack)) {
		printf("%d ", SPop(&stack));	
	}
	printf("\n");
	return 0;
}

잠시 짚고 넙어가기!
위의 main함수는 배열 기반 main함수의 코드와 동일하다!

중위 표기법/전위 표기법/ 후위 표기법
중위: 흔이 할고 있는 연산 표기법 으로 예시3+5*2 가 있다
전위: 전은 말그대로 앞을 말하는것으로 연산자와 피연사자 중에 연산자를 우선으로 앞으로 내세우는 것이다.
후위: 후는 말 그대로 뒤를 말하는 것으로 연산자와 피연산자 중에 연산자를 맨끝으로 내세우는 것이다.

중위 표기법을 후위 표기법으로
우선 예시로 4+53 이 있다 하자 이건 명백한 흔히 들 알고 있는 중위 표기법 이다. 이를 후위 표기법으로 바꾸기 위해선 보이는 피연산자는 한곳에 나열시키고 연사자는 스택에 쌓은다. 여기선 4를 우선으로 나열하고 그다음에 보이는 연산자인 +를 스택에 쌓고 다시 피연산자 5를 4 뒤에 나열시킨다. 그리고 연산자는 +연산자 위에 쌓은다. 그리고 끝으로 3을 나열시키면 우선 나열된 숫자는 453이다. 그 후 스택에 서 쌓은 연산자를 그대로 꺼내면 된다.(filo) 그럼 결과는 453*/ 이 나오는 걸 알 수 있다.

고려해야 할 점!
연산자의 경우 스택에 넣고 뺄때 우선순위가 매우 중요 하다. 예를들어 와 - 경우 가 우선순위가 높다 그럼에도 불구하고 스택에서 위에 -가 있다면 우선수위에 한하여 가 우선으로 출력된다. 허나 반대로 - 위에 * 가있다면 피연사자가 우선으로 나열 후 스택에서 연산자가 순차적으로 출력된다.

후위 표기법의 연산식
후위 표기법을 연산하기 위해서는 앞서 중위 표기법을 후위 표기법을 바꾸엇 듯이 이번엔 반대로 후위 표기법을 중위 표기법으로 바꾸어야 한다. 바꾸는 방법은 아래와 같다
피연산자를 만나면 스택에 삽입 -> 연산자를 만나면 필요한 한 만큼의 피연산자를 스택에서 꺼내 연산하고, 그 결과를 다시 스택에 삽입 -> 이 행위를 반복하여 마지막으로 스택에서 꺼내 출력

고려해야 할 점!
위에 연산식에서 연산 같은 경우 스택에 해당되니 밑에서 위의 순으로 연산하는걸 명심해라! 예를 들어 324 +의 경우 위의 공식에 따라 스택에는 324가 삽입 되고 연산자는 우선 를 써야 한다. 허나 여기서 중요해야 할 점은 2와 4 그리고 인데 연산의 순서가 42가 아닌 밑에서 위의 경우를 고려해 2*4라는 것을 명백히 알아두어여 한다!

큐 의 정의
앞서 설명한 스택의 특징에서는 먼저 들어온 것이 제일 나중에 나가는 반면 큐는 먼저 들어간 데이터가 먼저 나오는 구조 이다.

큐의 ADT
크게 2가지로 나뉘어 볼 수 있다
1. enqueue : 큐에 데이터를 넣는 연산
2. dequeue : 큐에서 데이커를 꺼내는 연산

큐의 구현 방법
큐는 크게 f(front) 와 r(rear) 로 나뉘어 볼 수 있는데 f가 가리키는 데이터가 저장순서가 가장 앞선 데이터 이므로 f가 가리키는 데이터를 대상으로 Dequeue 연산을 진행하고 r을 참조하여 enqueue 연산을 진행하여야 한다. 요약 하면 뒤로 넣고 앞으로 빼는 자료구조 이다

문제점
배열의 특성상 길이가 정해져 있는 상태로 데이터의 삽입과 삭제 행위가 일어 나고 있기 때문에 제한된 범위를 넘어가면 에라 상태가 변변히 일어난다. 이로 인해 나온 해결책이 원형 큐 이다

원형 큐의 구현 방법
r과 f를 회전시키는 특성을 가지고, r과 f를 완전히 채우고 또 와전히 비워보기 위해서는 매열을 꽉 채우지 않는 방법으로 구현을 한다. 즉 다시 말해 배열의 길이가 n이라면 데이터가 n-1개 채워 줬을때 꽉 찬 것으로 간주한다. 이로 인해 새롭게 추가 할수 있는 것은
1. 원형 큐가 텅 빈 상태 : f와r이 동일한 위치를 가리킨다
2. 원형 큐가 꽉 찬 상태 : r이 카리키는 위치의 앞을 f가 가리킨다.

열결 리스크 기반 큐
위에서는 배열 기반 큐를 구현해 보았다면 이번엔 연결 리스트 기반 큐를 구현 해 보려 한다. 전에 배웠던 스택과 큐의 연결 리스크 기반 차이가 있다면 그건 아마 삽입과 삭제 가 일어나는 위치가 다르다.

연결 리스트 기반 큐의 구현
배열 기반과 다르게 노드의 추가 과정은 둘로 나뉘어 진다. f와 r둘다 새 노드를 가리키게 하고 두번 째 이후 부터는 r이 새 노드를 가리키게 한다. 허나 이와 다르게삭제 과정에서는 둘로 나뉠 필요 없이 f만 가리키는 대상을 그 다음 노드로 변경시키고 f가 이전에 가리키는 노드를 삭재하는 방법으로 구현 하면 된다.

덱의 정의
큐와 비슷하지만 좀 다르게 앞으로도 뒤로고 넣을수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조 이다.

덱의 adt
크게 4가지로 나뉘어 볼 수 있다
dqadd_fisrt : 앞으로 넣기
dq_add_last : 뒤로 넣기
dq_remove_fisrt: 앞에서 뻬기
dq_remove_last 뒤에서 빼기

덱의 구현
앞서 adt를 참조하여 앞뒤 모든 곳에서 삽입과 삭제가 가능하게 하기 위해선 배열 과 단방형 연결리스가 아닌 양방형 연결 리스트가 제일 좋은 선택 방법이다.

트리의 정의
트리란 계층적 관계를 표현하는 자료구조 이다. 여기서 중요시하게 봐야하는 단어는 계층적이 아니라 표현 이라는 단어 이다. 앞서 보았던 선형 자료구조들은 무엇가를 저장하고 까내는 것이 전부 였다. 허나 이번에는 트리의 구조로 이뤄진 무엇인가를 표현하기에 적절한 정의를 끊임없이 탐구해야 한다.

트리의 기본적인 용어
노드(node): 트리의 구성요소에 해당하는 a,b,c,d,e,f와 같은 요소
간선(edge): 노드와 노드를 연결하는 연결선
루트 노드(root node): 트리 구조에서 최상위에 존해하는 a와 같은 노드
단말 노드(terminal node): 아래로 또 다른 노드가 연결되어 있지 않은 e,f,c,d와 같은 노드
내부 노드(interanl node): 단말 노드를 제외한 모든 노드로 a와 b 같은 노드

이진 트리와 서브 트리
우선 서브 트리란 큰 메인 트리에서 속해있는 작은 트리를 서브 트리라 한다. 즉 루트 노드는 포함 되 있지 않지만 단말 노드와 그 위의 내부 노드 만 포함되 있는것 을 뜻한다. 반면 이진트리는 간략하게 말해 자식 노득 간 두 개씩 달린 트리 입니다. 이진트리의 다음 조건은 아래와 같다.
루트 노드를 중심으로 두 개의 서브트리로 나뉘어 진다.
나뉘어진 두 서브 트리도 모두 이진 트리이여햐 한다.

포화 이진 트리와 완전 이진 트리
포화 이진 트리: 모든 레벨이 꽉찬 이진 트리를 말한다.
완전 이진 트리: 포화 이진 트리 처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 것을 뜻한다. 단 왼쪽 자식(단말)노드는 꼭 채워져야 있어만 완전 이진 트리에 부합하다.

이진 트리의 구현
노드의 생성 -> 노드에 저장된 데이터를 반환 -> 노드에 데이터를 저장 -> 왼쪽 서브 트리 주소값 반환 -> 오른쪽 서브 트리 주소값 반환

이진 트리의 순회
크게 3가지로 나뉘어 볼 수 있다
전위 순회: 루트 노드를 먼저
중위 순회: 루트 노드를 중간에!
후위 순회: 루트 노드를 마지막에!-