스택

◎ 스택

- 입출력형태 : 후입선출 (last in first out)
- 스택에서의 입출력은 맨위에서만 일어나고, 스택의 중간에서는 데이터를 삭제할 수 없다.
- 스택상단 : 입출력이 일어나는 부분 / 스택하단
- 스택은 특히 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우 긴요하게 사용가능.

◎ 추상 자료형 스택

- 추상자료형으로서의 스택은 0개 이상의 요소를 가지는 선형 리스트의 일종으로 정의

create (size)  // 최대크기가 size인 공백 스택을 생성
is_full(s) // 스택이 포화상태에 있는지 검사
is_empty(s) //스택이 공백상태에 있는지 검사
push(s, item) //삽입연산
pop(s) //삭제연산
peek(s) // 요소를 스택에서 삭제하지 않고 보기만 하는 연산

◎ 스택의 구현

1. 1차원 배열을 이용하여 구현 - 동적/정적
2. 연결리스트를 사용하여 구현

◎ 배열을 통한 구현 : 정적

전역변수 사용금지!

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100

int main(){
	int stack[MAX_STACK_SIZE]; //스택의 요소들을 저장할 배열 
	int top=-1; //가장 최근에 입력되었던 자료의 index
				//공백스택일 경우 top==-1이다.
	int i=0, value;
	
	while(scanf("%d", &stack[i])!=EOF)
		i++;
		top++;
	
	is_empty(top);
	is_full(top);
	
	printf("last input : ");
	scanf("%d", &value);
	
	push(stack, &top, value);
	pop(stack, top);
}

void is_empty(int top){
	if(top==-1) printf("empty\n");
	else printf("not empty\n");
}

void is_full(int top){
	if(top>=MAX_STACK_SIZE-1) printf("full\n");
	else printf("not full\n");
}

void push(int *stack, int *top, int value){
	if(*top>=MAX_STACK_SIZE-1)printf("overflow\n");	//is_full 함수 이용가 능 
	else
		*top+=1;
		stack[*top]=value;
}

void pop(int *stack, int top){
	if(top==-1) printf("underflow\n");
	else
		printf("pop : %d\n", stack[top]);
		top-=1;
		//여기서 stack[top]에 있는 요소를 굳이 삭제해야 할까??
		//이후에 들어온 새로운 요소가 덮어쓴다면 굳이 안해도 될것같다.
}

이때 요소가 다양해진다면 요소끼리 구조체로 묶어 사용하는 편이 효율적일것이다.

typedef struct{
	int student_no;
	char name[MAX_STRING];
	char address[MAX_STRING];
}element;

typedef struct{
	element data[MAX_STACK_SIZE];
	int top;
}stack;

◎ 배열을 통한 구현 : 동적

일단 동적메모리 할당을 이용하라고 했을때 대충 떠오른 코드는 아래와 같다.

int main(){
	stack *s;
	int size=1;
	s=(stack*)malloc(sizeof(stack));	//동적메모리할당 
	///
	if(s->top>=MAX_STACK_SIZE-1==0) 
		size++;
		realloc(s,sizeof(stack)*size);	//요소가 하나 추가될때 마다 메모리를 재할당해준다. 
 }

만약 새로운 요소를 추가하려고 하는데 함수가 full상태이면 realloc을 통해 메모리를 재할당받아야 할 것이다.

//교재에 나와있는 동적 배열 스택 프로그램  
#include<stdio.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct{
	element *data;
	int capacity;	//현재스택의크기! = 들어있는 요소의 수 
	int top; 
}stacktype;

void init_stack(stacktype *s){	//스택 생성 함수 
	s->top=-1;
	s->capacity=1;	
	s->data=(element*)malloc(s->capacity * sizeof(element)); 
}

int is_empty(stacktype *s){
	return (s->top==-1);	//공백이면 return !0, 공백이 아니면 return 0 
}

int is_full(stacktype *s){
	return (s->top==(s->capacity-1));	//포화면 return !0, 포화가 아니면 return 0 
}

void push(stacktype *s, element item){
	if(is_full(s)){
		s->capacity *=2;	//push 할때 포화상태면 용량을 2배로 늘린다. 
		s->data = (element*) realloc(s->data, s->capacity * sizeof(element));
	}
	s->data[++(s->top)] = item;
}

element pop(stacktype *s){
	if(is_empty(s)){
		printf("error"); 
	}
	else return s->data[(s->top)--];
}

int main(){
	stacktype s;
	init_stack(&s);
	push(&s, 1); 
	printf("%d\n", pop(&s));
	free(s.data);
}

교재에 나와있는 코드를 보니까 나의 생각이 짧았음을 깨달았다. 나는 stack이라는 구조체에 element와 top이 저장되어 있고 이런 stack *s에 동적메모리를 할당해주었다. 이런 방식은 스택이 여러개 있을때 해야할 방식이지 element를 추가할때는 쓸모가 없다. 내가 동적메모리 할당해주어야 할 대상을 날카롭게 찾는 연습이 필요할 듯 하다. 동적메모리할당이 확실히 아직 익숙하지가 않은 것 같다ㅠ 계속 동적으로 바뀌는 대상은 element이기 때문에 교재에 나온것처럼 element *data를 선언하고 이 포인터변수에 동적메모리를 할당하는 것이 맞다.