도전하라! 시작하라!

Last In First Out의 구조를 가진 " Stack "에 대해서 배워보자!

ex) 식당 아주머니는 식판을 아래에서부터 쌓아올리지만, 식판을 가져가는 우리는 위에서부터 가져간다!

     지역 변수의 사용

- 수직적인 구조이다.

- push : 스택이라는 메모리에 데이터를 저장하는 인터페이스

- pop :  스택이라는 메모리부터 데이터를 꺼내오는 인터페이스

프로젝트명 : 20140212

파일명 : 1.c

// 스택(Stack) : LIFO(Last In First Out)
// ex)식당에서의 식판, 지역 변수의 사용

// push : 스택이라는 메모리에 데이터를 저장하는 인터페이스
// pop : 스택이라는 메모리부터 데이터를 꺼내오는 인터페이스

#include <stdio.h>

#define MAX_SIZE	(5)

int arr[MAX_SIZE];
int idx;	//초기화해주지 않아도, os가 자체적으로 0으로 초기화

//push의 경우 뭘로 return할지 굳이 표시하지 않아도 된다.
void push(int data) {
	arr[idx++] = data;
	/* arr[idx] = data;	//최초의 push의 경우 0부터 시작한다고 했으니
	++idx; */
}

int pop() {
	return arr[--idx];
	/*
	--idx;
	return arr[idx]; */
}

//참(0 이외의 수)과 거짓(0)을 나타내려면 int 타입을 쓴다.
int is_full() {
	return (idx == MAX_SIZE);
	/*
	if(idx == MAX_SIZE)
		return 1;
	else
		return 0;
	*/
}

int is_empty() {
	return (idx ==0);
	/*
	if(idx ==0)
		return 1;
	else
		return 0;
	*/
}

void main() {
	int i;

	for(i=0; i<10; i++) {
		if(!is_full())	//가득 차 있지 않아야 push가능
			push(i+1);	//1 2 3 4 5 6 7 8 9 10
	}

	for(i=0; i<10; i++) {
		if(!is_empty())
			printf("%d\n", pop());
	}
}

step 1. 가장 간단한 스택의 구현

#include <stdio.h>

#define MAX_SIZE	(5)

int arr[MAX_SIZE];
int idx;	//초기화해주지 않아도, os가 자체적으로 0으로 초기화

void push(int data) {arr[idx++] = data;}
int pop() {	return arr[--idx]; }
int is_full() { return (idx == MAX_SIZE); }
int is_empty() { return (idx ==0); }

void main() {
	int i;

	for(i=0; i<10; i++) {
		if(!is_full())	//가득 차 있지 않아야 push가능
			push(i+1);	//1 2 3 4 5 6 7 8 9 10
	}

	for(i=0; i<10; i++) {
		if(!is_empty())
			printf("%d\n", pop());
	}
}

step2. 하나 이상의 자료구조 구현

//step 2. 하나 이상의 자료구조 구현!
#include <stdio.h>

#define MAX_SIZE	(5)

// 데이터 추상화를 ADT(Abstract Data Type)
typedef struct __STACK {
	int arr[MAX_SIZE];
	int idx;
} STACK;

int arr[MAX_SIZE];
int idx;	//초기화해주지 않아도, os가 자체적으로 0으로 초기화

void push(int data, STACK *s) { s->arr[(s->idx)++] = data; }
int pop(STACK *s) {	return s->arr[--(s->idx)];}
int is_full(STACK *s) {	return (s->idx == MAX_SIZE);}
int is_empty(STACK *s) { return (s->idx ==0);}

void main() {
	int i;
	STACK s = {0, };	//이 데이터를 어떻게 처리할지는 라이브러리 개발하고 분석한 사람만 사용할 수 있다.
	//라이브러리 개발자가 저 스택을 초기화해줘야한다. -> step3

	for(i=0; i<10; i++) {
		if(!is_full(&s))	//가득 차 있지 않아야 push가능
			push(i+1, &s);	//1 2 3 4 5 6 7 8 9 10
	}

	for(i=0; i<10; i++) {
		if(!is_empty(&s))
			printf("%d\n", pop(&s));
	}
}

step3. 자료구조의 초기화를 위한 인터페이스 지급

// step 3 : 자료구조의 초기화를 위한 인터페이스 지급
// 스택의 크기가 고정되어있고,  사용자가 우너하는 시점에 메모리를 할당해야하기때문ㅇ ㅔ자료구조로...->step4
#include <stdio.h>

#define MAX_SIZE	(5)

// 데이터 추상화를 ADT(Abstract Data Type)
typedef struct __STACK {
	int arr[MAX_SIZE];
	int idx;	// =0;	//?
} STACK;

void init_stack(STACK *s) { s->idx = 0; }
void push(int data, STACK *s) { s->arr[(s->idx)++] = data; }
int pop(STACK *s) {	return s->arr[--(s->idx)];}
int is_full(STACK *s) {	return (s->idx == MAX_SIZE);}
int is_empty(STACK *s) { return (s->idx ==0);}

void main() {
	int i;
	STACK s;
	init_stack(&s);

	for(i=0; i<10; i++) {
		if(!is_full(&s))	//가득 차 있지 않아야 push가능
			push(i+1, &s);	//1 2 3 4 5 6 7 8 9 10
	}

	for(i=0; i<10; i++) {
		if(!is_empty(&s))
			printf("%d\n", pop(&s));
	}
}

step4. 자료 구조를 힙에 구현

// step 4.  자료구조를 힙에 구현
#include <stdio.h>
#include <stdlib.h>

typedef struct __STACK {
	#define MAX_SIZE	(5)
	int *arr;	//힙에 구현
	int idx;
} STACK;

void init_stack(STACK *s) { 
	s->arr = (int*)malloc(sizeof(int)*MAX_SIZE);
	s->idx = 0;
}
void push(int data, STACK *s) { s->arr[(s->idx)++] = data; }
int pop(STACK *s) {	return s->arr[--(s->idx)];}
int is_full(STACK *s) {	return (s->idx == MAX_SIZE);}
int is_empty(STACK *s) { return (s->idx ==0);}

void main() {
	int i;
	STACK s;
	init_stack(&s);

	for(i=0; i<10; i++) {
		if(!is_full(&s))	//가득 차 있지 않아야 push가능
			push(i+1, &s);	//1 2 3 4 5 6 7 8 9 10
	}

	for(i=0; i<10; i++) {
		if(!is_empty(&s))
			printf("%d\n", pop(&s));
	}
}

step5. 범용 타입에 대한 설계------------------------------

// step 5. 범용 타입에 대한 설계
#include <stdio.h>
#include <stdlib.h>

typedef struct __STACK {
	#define MAX_SIZE	(5)
	int *arr;	//모든 타입이 다 되게 해야 될 때는 void 포인터 타입으로
	int idx;
} STACK;

void init_stack(STACK *s) { 
	s->arr = (int*)malloc(sizeof(int)*MAX_SIZE);
	s->idx = 0;
}
void push(int data, STACK *s) { s->arr[(s->idx)++] = data; }
int pop(STACK *s) {	return s->arr[--(s->idx)];}
int is_full(STACK *s) {	return (s->idx == MAX_SIZE);}
int is_empty(STACK *s) { return (s->idx ==0);}

void main() {
	int i;
	STACK s;
	init_stack(&s);

	for(i=0; i<10; i++) {
		if(!is_full(&s))	//가득 차 있지 않아야 push가능
			push(i+1, &s);	//1 2 3 4 5 6 7 8 9 10
	}

	for(i=0; i<10; i++) {
		if(!is_empty(&s))
			printf("%d\n", pop(&s));
	}
}

------------------------------------

// 스택의 내부 자료구조를 리스트로 구현!
#include <stdlib.h>
#include <stdio.h>

typedef struct __NODE
{
	int data;
	struct __NODE *next;
} NODE;

typedef struct __STACK
{
	int idx;	// 스택에 저장된 위치
	int size;	// 스택의 크기
	struct __NODE *head;
} STACK;

void init_stack(STACK *s, int size)
{
	s->idx = 0;
	s->size = size;
	s->head = 0;
}

void push(int data, STACK *s) {
	NODE *cur;
	NODE *node = (NODE*)malloc(sizeof(NODE));
	node->data = data;
	node->next = 0;

	// 리스트가 비어 있는 경우
	if(s->head ==0) {
		s->head = node;
		++(s->idx);
		return;
	}

	// 리스트가 비어 있지 않은 경우
	cur = s->head;
	while(cur->next)
		cur = cur->next;

	cur->next = node;

        ++(s->idx);

}

int pop(STACK *s)
{
	int data;
	NODE *prev = s->head;
	NODE *cur = s->head;

	while(cur->next)
	{
		prev = cur;
		cur = cur->next;
	}

	data = cur->data;
	prev->next = 0;
	--(s->idx);
	free(cur);

	return data;
}

int is_full(STACK *s) { return s->size == s->idx; }
int is_empty(STACK *s) { return s> idx == 0; }

void main()
{
	int i;

	STACK s;
	init_stack(&s, 3);

	for(i = 0; i < 4; i++)
	{
		if(!is_full(&s)) push(i+1, &s);
	}

	for(i = 0; i < 4; i++)
	{
		if(!is_empty(&s)) printf("%d\n", pop(&s));
	}
}

------------------

파일명 : 2.c

//비트셋(Bitset, Bitmap
// LED 제어 프로그램 - 메모리의 낭비가 일어나고있다.
#include <stdio.h>
#include <stdlib.h>


enum { LED0 = 0, LED1, LED2, LED3, LED4, LED5, LED6, LED7 };
enum { LED_OFF = 0, LED_ON = 1 };
void main()
{
	int i;
	char mmio[8] = {0, };

	// LED ON
	mmio[LED1] = LED_ON;
	mmio[LED3] = LED_ON;

	// LED CHECK
	for(i=0;i<8;i++){
		if(mmio[i] == LED_ON)
			printf("LED%d ON\n", i);
		else
			printf("LED%d OFF\n", i);
	}
	getchar(); system("cls");

	// LED OFF
	mmio[LED3] = LED_OFF;

	// LED CHECK
	for(i=0;i<8;i++){
		if(mmio[i] == LED_ON)
			printf("LED%d ON\n", i);
		else
			printf("LED%d OFF\n", i);
	}
}

위의 소스코드는 메모리의 낭비라는 문제점이 있다. 다음 소스코드는 그를 수정하였다.

// 문제점: 메모리의 낭비
#include <stdio.h>
#include <stdlib.h>

enum { LED0 = 0, LED1, LED2, LED3, LED4, LED5, LED6, LED7 };
enum { LED_OFF = 0, LED_ON = 1 };

// 비트 연산으로 변경해보세요!

// 시프트 연산자

// 데이터 << 이동할 비트 수
// 데이터 >>  이동할 비트 수

// LED 제어 프로그램 - 메모리의 낭비가 일어나고있다.

void main()
{
	int i;
	char mmio = 0;	// // char mmio[8] = { 0, };

	// LED ON
	mmio = mmio | (LED_ON << LED1);	// 0000 0000 mmio = 0
									// 0000 0010 LED_ON	<< LED1
									// --------- |(OR)
									// 0000 0010
	
	mmio |= LED_ON >> LED3;			// 복합 대입 연산자의 사용
	// 규칙 1. 특정 비트를 설정하려면 OR 연산자를 사용해야 한다!


	// 0000 1010
	// 0000 0010	// 마스크 비트
	// --------- &
	// 0000 0010

	// LED CHECK
	for(i=0; i<8; i++)
	{
		if(mmio & (LED_ON << i))	// 0000 1010 & 1 << i
			printf("LED%d ON\n", i);
		else
			printf("LED%d OFF\n", i);
	}
	// 규칙 2. 특정 비트를 검사하려면 &연산자를 사용해야 한다.

	getchar(); system("cls");

	// LED OFF
	//mmio[LED3] = LED_OFF;	// 0000 1010
							// 1111 0111	~(LED_ON << LED3)
							// --------- &
							// 0000 0010
	mmio &= ~(LED_ON << LED3); //비트를 끈거다.

	// 규칙 3. 특정 비트를 초기화하려면 &연산자와 비트 반전 연산자(~)
	// 를 사용해야 한다.

	// LED CHECK
	for(i=0; i<8; i++)
	{
		if(mmio & (LED_ON << i))
			printf("LED%d ON\n", i);
		else
			printf("LED%d OFF\n", i);
	}
}

c

#include <stdio.h>
#include <stdlib.h>

#define BIT_SET(i , x)  ((x[i/32]) |= (1>>(i%32)))
#define BIT_ISSET(i , x) ((x[i/32]) & (i >>(>i%32)))
#define BIT_CLR(i , x)  ((x[[i/32]) &= ~(i <>>(i%32)))

enum { LED0 = 0, LED1, LED2, LED3, LED4, LED5, LED6, LED7 };
enum { LED_OFF = 0, LED_ON = 1 };

// 비트 연산으로 변경해보세요!

// 시프트 연산자

// 데이터 << 이동할 비트 수
// 데이터 >> 이동할 비트 수

void main()
{
	int i;
	//char mmio = 0;	// 32비트 -> 128비트
	int mmio[32] = {0,};
	// LED ON

	BIT_SET(LED1, mmio);
	BIT_SET(1000, mmio);
	//mmio = mmio | (LED_ON <<LED1);	// 0000 0000 mmio = 0
	// 0000 0010 LED_ON	<< LED1
	// --------- |(OR)
	// 0000 0010

	// 복합 대입 연산자의 사용



	for (i = 0; i<1024; i++)
	{
		if (BIT_ISSET(i, mmio))	// 0000 1010 & 1 << i
			printf("LED%d ON\n", i);
		else
			printf("LED%d OFF\n", i);
	}

	getchar(); system("cls");


	mmio &= ~(LED_ON << LED3);


	// LED CHECK
	for (i = 0; i<128; i++)
	{
		if (BIT_CLR(i, mmio))
			printf("LED%d ON\n", i);
		else
			printf("LED%d OFF\n", i);
	}
}

e

f

파일명 : 3.c

//Dynamic Array
#include <stdio.h>

#define ARR_SIZE(x)	(sizeof(arr)/sizeof(*arr))

int sum_arr(int arr[]) {
	int i, sum = 0;
	for(i=0;i<ARR_SIZE(arr);i++) {
		sum += arr[i];
	}
	return sum;
}

void main() {
	int i, sum = 0;
	int arr[] = {1,2,3,4,5,6,7,8,9,10};

	//for(i=0;i<ARR_SIZE(arr);i++)
	//	sum += arr[i];

	printf("sum=%d\n", sum_arr(arr));
}

a

//이 소스코드의 단점 : 배열에 있는 컨텐츠를 저장하는데, 저장되는 타입이 int이다. 
//근데 앞으로 double, float, char타입의 배열이 만들수도있는거다. 
//즉 모든 것이 성립하는 void 타입으로 바꿔야 할것이다.
//즉 int타입만 저장 가능하다
#include <stdio.h>
#include <stdlib.h>	//calloc 사용하기 위해서 선언한다.

typedef struct __Array {
	int capacity;
	int *content;
} Array;

Array* createArray(int capacity) {
	Array *arr = (Array*)calloc(1, sizeof(struct __Array));
	arr->content = (int*)calloc(capacity, sizeof(int));
	arr->capacity = capacity;

	return arr;
}

int setElement(Array *arr, int index, int data) {
	int capacity = arr->capacity;
	if(index <0 || index >=capacity)
		return -1;

	arr->content[index] = data;
	return 0;
}

int getElement(Array *arr, int index) {
	int capacity = arr->capacity;
	if(index <0 || index >capacity) {
		fprintf(stderr, "out of index");
		exit(-1);
	}

	return arr->content[index];
}

int getCapacity(Array *arr) { return arr->capacity; }

int sum_arr(Array *arr) {
	int i, sum = 0;
	for(i=0;i<getCapacity(arr);i++)
		sum +=getElement(arr, i);
	return sum;
}

void main() {
	int i;
	Array *arr = createArray(5);	//int arr[5];만든것과 동일

	for(i=0;i<getCapacity(arr);i++) {
		setElement(arr, i, i+1); //arr[i] = i+1;
	}

	printf("sum = %d\n", sum_arr(arr));

	/*for(i=0;i<getCapacity(arr);i++)
		printf("arr[%d] = %d\n", i, getElement(arr, i));
		printf("arr[%d] = %d\n", i, arr[i]);	//이건 안된다. 왜냐하면 arr은 배열이아니라 구조체니까 */
 }

// 문제점: 특정 타입만을 저장할 수 있음!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct __Array
{
	int capacity;
	void **content;
} Array;

Array* createArray(int capacity)
{
	Array *arr = (Array*)calloc(1, sizeof(struct __Array));
	arr->content = (void**)calloc(capacity, sizeof(void*));
	arr->capacity = capacity;

	return arr;
}

void* setElement(Array *arr, int index, void *pointer)
{
	void *old;
	int capacity = arr->capacity;
	if(index < 0 || index>= capacity)
	{
		fprintf(stderr, "out of index");
		exit(-1);
	}


	old = arr->content[index];	// backup
	arr->content[index] = pointer;
	return old;
}

void* getElement(Array *arr, int index)
{
	int capacity = arr->capacity;
	if(index < 0 || index > capacity)
	{
		fprintf(stderr, "out of index");
		exit(-1);
	}

	return arr->content[index];
}

int getCapacity(Array *arr) { return arr->capacity; }

typedef struct
{
	char name[32];
	int  age;
} PERSON;


void main()
{
	int i;
	PERSON *p;
	Array *arr = createArray(5);	// int arr[5];
									// int[] arr = new int[5];
	for(i = 0; i < getCapacity(arr); i++)
	{
		p = (PERSON*)malloc(sizeof(PERSON));
		strcpy(p->name, "kkk");
		p->age = i+1;

		setElement(arr, i, p); // arr[i] = i+1;
	}

	for(i = 0; i < getCapacity(arr); i++)
	{
		p = (PERSON*)getElement(arr, i);
		printf("arr[%d] = %s, %d\n", i, p->name, p->age);
	}


	// printf("sum = %d\n", sum_arr(arr));

	//for(i = 0; i< getCapacity(arr); i++)
	//	printf("arr[%d] = %d\n", i, getElement(arr, i));	// printf("arr[%d] = %d\n", i, arr[i]);
}

// append 기능 추가
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct __Array
{
	int capacity;
	int size;	//배열의 현재 크기
	void **content;

} Array;

Array* createArray(int capacity)
{
	Array *arr = (Array*)calloc(1, sizeof(struct __Array));
	arr->content = (void**)calloc(capacity, sizeof(void*));
	arr->capacity = capacity;

	return arr;
}

void* setElement(Array *arr, int index, void *pointer)
{
	void *old;
	int capacity = arr->capacity;
	if(index < 0 || index >= capacity)
	{
		fprintf(stderr, "out of index");
		exit(-1);
	}


	old = arr->content[index];	// backup
	arr->content[index] = pointer;
	return old;
}

int addElement(Array *arr, void *pointer) {
	int size = arr->size;
	int capacity = arr->capacity;

	if(size == capacity)
		return -1;

	arr->content[size] = pointer;
	arr->size++;

	return 0;
}

void* getElement(Array *arr, int index)
{
	int capacity = arr->capacity;
	if(index < 0 || index > capacity)
	{
		fprintf(stderr, "out of index");
		exit(-1);
	}

	return arr->content[index];
}

int getCapacity(Array *arr) { return arr->capacity; }
int getSize(Array *arr) {return arr->size; }

typedef struct
{
	char name[32];
	int  age;
} PERSON;

void display(Array *arr){
	PERSON *p;
	int i;

	system("cls");
	for(i=0;i<getSize(arr);i++){
		p = (PERSON*)getElement(arr, i);
		printf("arr[%d] = %s, %d\n", i, p->name, p->age);
	}
	getchar();
}

void main()
{
	int i;
	PERSON *p;
	Array *arr = createArray(5);

	display(arr);
	for(i = 0; i < getCapacity(arr); i++)
	{
		p = (PERSON*)malloc(sizeof(PERSON));
		strcpy(p->name, "kkk");
		p->age = i+1;

		addElement(arr, p);

		display(arr);
	}

	for(i = 0; i < getCapacity(arr); i++)
	{
		p = (PERSON*)getElement(arr, i);
		printf("arr[%d] = %s, %d\n", i, p->name, p->age);
	}
}

1.c

2.c

3.c