정수 배열 스택 프로그램

전역 변수로 구현한 스택

1차원 배열과 top변수를 모두 전역 변수로 구현한다.
전역 변수로 구현되기 때문에 배열이나 top 변수를 함수의 매개 변수로 전달할 필요가 없다.
스택에 저장되는 데이터의 타입은 typedef을 이용하여 element로 저장되었다.
현재는 정수형으로 정의되어 있다.

구현

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

/*
정수 배열 스택 프로그램

전역 변수로 구현한 스택
*/

#define MAX_STACK_SIZE 100 //스택의 최대 크기
typedef int element;  //데이터의 자료형
element stack[MAX_STACK_SIZE]; //1차원 배열
int top = -1;



//공백 상태 검출
int is_empty() {
    return (top == -1);
}

//포화 상태 검출
int is_full() {
    return (top == (MAX_STACK_SIZE - 1));
}

void push(element item) {
    if (is_full()) {
        fprintf(stderr, "스택 포화 에러 \n");
        return;
    }
    else {
        stack[++top] = item;
    }
}

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

//peek 함수

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;
}

구조체 배열 스택 프로그램

만약 스택에 저장되어야하는 값이 정수나 문자가 아니고, 더 복잡한 구조를 갖는 요소이면?
예를 들어 학생에 대한 정보라면 학생의 학번, 이름, 주소 등의 정보가 요소에 포함되어야 할 것이다.

이런 경우에는 스택에 구조체를 저장하면 된다.

구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100 //스택의 최대 크기
#define MAX_STRING 100

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

element stack[MAX_STACK_SIZE];
int top = -1;



//공백 상태 검출
int is_empty() {
    return (top == -1);
}

//포화 상태 검출
int is_full() {
    return (top == (MAX_STACK_SIZE - 1));
}

void push(element item) {
    if (is_full()) {
        fprintf(stderr, "스택 포화 에러 \n");
        return;
    }
    else {
        stack[++top] = item;
    }
}

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

//peek 함수

element peek() {
    if (is_empty()) {
        fprintf(stderr, "스택 공백에러\n");
        exit(1);
    }
    else {
        return stack[top];
    }
}

int main(void) {

    element ie = { 20210823,
                    "MINCODEHUB",
                     "Seoul" };
    element oe;


    push(ie);
    oe = pop();

    printf("학번: %d\n", oe.student_no);
    printf("학번: %s\n", oe.name);
    printf("학번: %s\n", oe.address);
    return 0;
}

일반적인 배열 스택 프로그램 - StackType 구조체 배열 스택

stack 배열과 top이 전역 변수로 선언이 되면
하나의 프로그램에서 여러 개의 스택을 동시에 사용하기가 어렵다.

최근의 C++이나 자바의 경우에는 이 문제를 객체 지향의 개념을 이용하여 우아하게 해결할 수 있다.

C에서는 top과 stack 배열을 StackType이라는 새로운 구조체로 결합시키고
이 구조체의 포인터를 함수로 전달한다.

포인터들을 각 함수의 매개변수로 전달하는 것이다.
s -> top
s-> stack

이렇게 하면 여러개의 스택을 쉽게 만들 수 있다.

필요할 때마다 StructType을 사용하여 구조체를 만들면 된다.
-> StackType stack1, stack2;

구현

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

//포화 상태 검출
int is_full(StackType* s) {
    return (s -> top == (MAX_STACK_SIZE - 1));
}

void push(StackType* s, element item) {
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러 \n");
        return;
    }
    else {
        s->data[++(s->top)] = item;
    }
}

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

//peek 함수

element peek(StackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백에러\n");
        exit(1);
    }
    else {
        return s->data[s->top];
    }
}

int main(void) {
    StackType stack1, stack2;
    init_stack(&stack1);
    init_stack(&stack2);

    push(&stack1, 1);
    push(&stack1, 2);
    push(&stack1, 3);

    push(&stack2, 10);
    push(&stack2, 20);
    push(&stack2, 30);

    printf("%d\n", pop(&stack1));
    printf("%d\n", pop(&stack1));
    printf("%d\n", pop(&stack1));

    printf("%d\n", pop(&stack2));
    printf("%d\n", pop(&stack2));
    printf("%d\n", pop(&stack2));
    return 0;
}

동적 배열 스택 프로그램

동적 메모리 할당을 이용하여 스택을 생성
사용이 끝난 후에는 반드시 동적 메모리를 반환해야한다.

1차원 배열: 컴파일 시간에 크기가 결정된다.
동적 매열 : 실행 시간에 메모리 할당

동적 메모리 할당방식을 사용하면 필요할 때마다 스택의 크기를 동적으로 늘릴 수 있다.

구현

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

typedef int element;

typedef struct {
    element *data; //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);
}

//포화 상태 검출
int is_full(StackType* s) {
    return (s->top == (s->capacity - 1));
}

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;
    
}

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

//peek 함수

element peek(StackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백에러\n");
        exit(1);
    }
    else {
        return s->data[s->top];
    }
}

int main(void) {
    StackType s;
    init_stack(&s);
  //  init_stack(&stack2);

    push(&s, 1);
    push(&s, 2);
    push(&s, 3);

    //push(&stack2, 10);
   // push(&stack2, 20);
   // push(&stack2, 30);

    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));

   // printf("%d\n", pop(&stack2));
   // printf("%d\n", pop(&stack2));
  //  printf("%d\n", pop(&stack2));

    free(s.data);
  //  free(stack2.data);
    return 0;
}