[자료구조] - 스택

스택 : First in Last out 처음에 들어가서 마지막에 나온다.

스택을 구현하기 전에 추상 자료형으로 정의해 보자.

추상자료형

• 객체 : 0개 이상의 데이터를 가지는 유한 선형 리스트
• 연산 :

create(size) -> 최대 크기가 size인 공백 스택을 생성
is_full(s) -> 
		if(스택의 데이터수 == size) return true;
		else return false;
is_empty(s) ->
		if(스택의 데이터수 == 0) return true;
        else return false;
push(s, item) ->
		if( is_full(s) ) return Error_StackFull;
        else 스택의 맨 위에 item을 넣는다.
pop(s) ->
		if( is_empty(s) ) return Error_StackEmpty;
        else 스택의 맨 위에 데이터를 제거해서 반환한다.
peek(s) ->
		if( is_empty(s) ) return Error_StackEmpty;
        else 스택의 맨 위의 원소를 제거하지 않고 반환한다. 		

스택의 구현

먼저 스택에서 가장 최근에 입력되었던 자료를 기리키는 top 변수가 필요하다. 스택의 인덱스 역할을 하는 변수인데 비어 있으면 -1의 값을 갖는다.
그 이유는 배열의 인덱스가 0부터 시작하므로 0부터 데이터가 있기 때문이다. 위의 추상 자료형을 이용하여 스택을 전역변수, 1차원 배열로 구현해보자

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

#define MAX_STACK_SIZE 100 	// 스택의 최대 크기
typedef int element // 스택에 저장되는 데이터의 타입을 element로 정의
element stack[MAX_STACK_SIZE];	//배열을 이용한 스택
int top = -1;

//포화 상태 검출 함수
int is_full(){
	return (top == (MAX_STACK_SIZE -1)) //0~99//99면 1 아니면 0 반환
}

//공백 상태 검출 함수
int is_empty(){
	return (top == -1);	// top이 -1이면 1 아니면 0반환
}

//삽입 함수
void push(element item){
	if( is_full() ){
		fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else stack[++top] = item;// top = -1이기에 배열의 0부터 시작
}

//삭제 함수
element pop(){
	if( is_empty() ){
    	fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return stack[top--];
}

//피크 함수
element peek(){
	if( is_empty() ){
		fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return stack[top];
    
int main(void){

	push(1);
    push(2);
    push(3);
    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d\n", pop());
    return 0
 }

empty, full, push, pop, peek 함수를 구현해 보았으니 저 함수들을 가져다 쓰고 스택에는 데이터 타입을 바꾸기만 하면 쉽게 응용할 수 있다.

typedef int element 부분을

typedef struct studentinfo {
	int student_no;
    char name[100];
    char adress[100];
}element; 		이런식으로 바꾸고 

main() 함수안에서
	element ie = {2019158016, "ParkJunsu", "경기도 수원" };
	element oe;
	push(ie);
	oe = pop();

	printf("학번 : %d\n", oe.student_no);
	printf("이름 : %s\n", oe.name);
	printf("주소 : %s\n", oe.address);

이런식으로 바꾸면 element타입이 구조체가 될 수 있다. 

위의 방식은 stack 배열과 top이 전역변수로 선언되기 떄문에 하나의 프로그램에서 여러 개의 스택을 동시에 사용하기가 어렵다. 따라서 Stacktype이라는 새로운 구조체 타입을 만들고 필요할 때마다 Stacktype을 사용하여 구조체를 만들면 된다. 이렇게 하면 쉽게 여러 개의 스택을 만드는것이 가능하다.

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

#define MAX_STACK_SIZE 100 	// 스택의 최대 크기
typedef int element 
typedef struct {					// 스택이 구조체로 정의됨
 	element data[MAX_STACK_SIZE];
    int top;
} StackType;

//스택 초기화 함수
void init_stack(StackType *s){
	s->top = -1;
}

//포화 상태 검출 함수
int is_full(StackType *s){
	return (s->top == (MAX_STACK_SIZE -1)) //0~99//99면 1 아니면 0 반환
}

//공백 상태 검출 함수
int is_empty(StackType *s){
	return (s->top == -1);	// top이 -1이면 1 아니면 0반환
}

//삽입 함수
void push(Stacktype *s, element item){
	if( is_full(s) ){
		fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else s->data[++(s->top)] = item;// top = -1이기에 배열의 0부터 시작
}

//삭제 함수
element pop(Stacktype *s){
	if( is_empty(s) ){
    	fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}

//피크 함수
element peek(Stackype *s){
	if( is_empty(s) ){
		fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)];
    
int main(void){

	Stacktpe s;
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    return 0;
 }

동적 메모리 할당을 받아 스택을 구현해보자.

#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_full(StackType *s){
	return (s->top == (s->capaciy -1));
}

//공백 상태 검출 함수
int is_empty(StackType *s){
	return (s->top == -1);	// top이 -1이면 1 아니면 0반환
}

//삽입 함수
void push(Stacktype *s, element item){
	if( is_full(s) ){
		s->capacity *= 2;
        s->data =
        	(element *)realloc(s->data, s->capacity * sizeof(element));
    }
    s->data[++(s->top)] = item;// top = -1이기에 배열의 0부터 시작
}

//삭제 함수
element pop(Stacktype *s){
	if( is_empty(s) ){
    	fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}

//피크 함수
element peek(Stackype *s){
	if( is_empty(s) ){
		fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)];
    
int main(void){

	Stacktpe s;
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    return 0;
    free(s.data); // 동적할당 반환
 }