Stack이란?
: 데이터를 일시적으로 저장하는 방법
LIFO (Last In First Out, 후입선출)의 구조로나중에 들어온 데이터가 먼저 나가는 방식
배열을 크게 잡고 사용하여도 되지만 학습을 위하여 malloc을 사용하였다.
typedef struct
{
int size;
int idx;
int *data;
}Stack;
void DelStack(Stack *s){
free(s->data);
}
int initStack(Stack *s, int size){
s->size=size;
s->idx=-1;
s->data=(int*)malloc(sizeof(int)*(s->size));
if(s->data!=NULL){
return 1;
}else{
s->size=0;
return 0;
}
}구조체 Stack의 멤버 변수로는 스택의 크기 : size , 데이터 index : idx , 데이터 : *data
initStack을 통해 스택 구조체를 초기화한다.
idx는 -1로 초기화하고 malloc이 실패했을때 initStack이 0을 리턴하도록 한다.
int isFullStack(Stack *s){
if(s->idx>=s->size-1){
return 1;
}else{
return 0;
}
}
int isEmptyStack(Stack *s){
if(s->idx==-1){
return 1;
}else{
return 0;
}
}
int pushStack(Stack *s, int data){
if(isFullStack(s)){
// printf("Stack is Full\r\n");
return 0;
}else{
s->idx++;
s->data[s->idx]=data;
return 1;
}
return 0;
}
int popStack(Stack *s){
int val=0;
if(isEmptyStack(s)){
// printf("stack is Empty");
return val;
}else{
val=s->data[s->idx];
s->idx--;
return val;
}
}isFullStack : 스택이 가득 찼는지 확인
isEmptyStack: 스택이 비었는지 확인
pushStack : 스택에 데이터 삽입
-> 스택이 가득 차지 않았을 경우, 데이터 인덱스를 옮기고 데이터를 넣는다.
idx를 -1로 초기화 하였기 때문에 idx를 먼저 더해서 옮기고 데이터를 넣었다. 만약 idx를 0으로 초기화하였다면 데이터를 넣고 idx를 더해주면 된다.
popStack : 스택에서 데이터 출력
->스택이 비어있지 않을 경우, 데이터를 출력하고 인덱스를 옮긴다.
int SearchStack(Stack *s, int data){
int i;
for(i=0;i<s->idx;i++){
if(data==s->data[i]){
return i;
}
}
return -1;
}조금의 응용으로 SearchStack은 스택에 찾으려는 데이터가 있으면 해당 인덱스를 없으면 -1을 리턴하도록 만들어보았다.
만든 함수를 아래와 같이 테스트하였다.
int main(){
int i;
Stack stack;
initStack(&stack,10);
pushStack(&stack,1);
pushStack(&stack,2);
pushStack(&stack,3);
pushStack(&stack,4);
pushStack(&stack,5);
pushStack(&stack,6);
pushStack(&stack,7);
pushStack(&stack,8);
pushStack(&stack,9);
pushStack(&stack,10);
pushStack(&stack,11);
printf("search %d %d\r\n",SearchStack(&stack,7),SearchStack(&stack,-1));
for(i=0;i<13;i++){
printf("% d idx:%d\r\n",popStack(&stack),stack.idx);
}
DelStack(&stack);
return 0;
}
1. 크기가 10인 사이즈를 만들고 11개의 데이터를 넣었다. - > Stack is Full 출력
2. 데이터가 7인 인덱스와 -1인 인덱스를 서치하였다 -> serach 6 -1 출력
3. 13개의 데이터를 출력하였다 -> 10 idx : 9~~ stack is Empty 0 idx : -1 출력
끝
'지식저장소 > C' 카테고리의 다른 글
| [C] Ring Buffer / 링버퍼 구현 (0) | 2022.03.29 |
|---|---|
| [C/BOJ] 9012 괄호 - Stack이용 (0) | 2022.02.16 |
| [C/STM32] Uart로 printf 대신하기 (0) | 2022.01.14 |
| [C] Hex Convert to HexString And HexString Convert to Hex (0) | 2021.10.26 |
| [C] ARIA 128 암호화 (2) | 2021.09.03 |
