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
0.exe
