스택

스택

정의

• 쌓아놓은 더미

구조

• LIFO 구조 (Last - In - First - Out) : 가장 최근의 데이터가 가장 먼저 나감
• pop() : 스택에 데이터를 삭제
• push () : 스택에 데이터를 추가

예제

• 스택 추상데이터타입(ADT)
• • 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 스택의 맨 위의 원소를 제거하지 않고 반환한다

구현(스스로 해보기)

소스코드 위치

#define _CRT_SECURE_NO_WARNINGS
#define MAX_STACK_SIZE 100
#define ERROR_STACKFULL -1
#define ERROR_STACKEMPTY -2
/*
error 목록
return -1 : ERROR_STACKFULL
return -2 : ERROR_STACKEMPTY
*/

#include <stdio.h>

typedef int element;
element stack[MAX_STACK_SIZE];    // stack 생성
int idx = -1;
int item = 0;

int is_full() {
    if (idx + 1 == MAX_STACK_SIZE)
        return 1;
    else
        return 0;
}

int is_empty() {
    if (idx == -1)
        return 1;
    else
        return 0;
}

int push(element *s, int item) {
    if (is_full())
        return ERROR_STACKFULL;

    else {
        s[idx++] = item;
        return 1;
    }
}

int pop(element* s) {
    printf("%d\n", idx);
    if (is_empty())
        return ERROR_STACKEMPTY;

    else s[idx--];
}

int peek(element* s) {
    return s[idx];
}

int main(void) {
    push(stack, 1);
    push(stack, 2);
    printf("%d", pop(stack));
}

🤔문제점

1. pop이 제대로 실행 안됨
2. 굳이 포인터를 사용해서 전역변수에 접근할 필요가 없었음
3. return 값 때문에 쓸데없는 반환 및 코드가 늘어남.

구현 (정답 코드)

소스코드 위치

#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--];
}
// 피크 함수
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;
}

 

🤔참고할 점

1. fprintf를 사용하여 함수 내에서 바로 에러 처리를 함 -> 코드의 간략화 및 순서도의 최적화
2. stack full과 stack empty를 판단하는 함수는 바로 비교연산을 리턴함으로서 훨씬 직관적이면서 간략한 코드가 완성됨
3. 전역으로 선언한 stack을 굳이 포인터로 참조하여 사용하지 않음.

스택 응용

---

구조체 스택(스스로 해보기)

소스코드 위치

#define _CRT_SECURE_NO_WARNINGS
#define MAX_STACK_SIZE 100

#include <stdio.h>
#include <stdlib.h>
typedef int element;

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

void init_stack(StackType* s) {
    /*for (int i = 0; i < MAX_STACK_SIZE; i++) {
        s->data[i] = NULL;
    }*/
    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, "STACK IS FULL!");
        exit(-1);
    }

    else {
        s->data[++(s->top)] = item;
    }
}

element pop(StackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "STACK IS EMPTY!");
        exit(-1);
    }
    else {
        element re = s->data[s->top];
        s->data[s->top] = NULL;
        (s->top)--;
        return re;
    }
}

int main(void) {
    StackType Stack;
    init_stack(&Stack);
    for (int i = 0; i < 100; i++) {
        push(&Stack, i);
        printf("push [%d] -> %d\n", Stack.top, Stack.data[i]);
    }
    printf("=====================================\n");

    for (int i = 0; i < 100; i++) {
        printf("pop [%d] -> %d\n",Stack.top, pop(&Stack));
    }
}

구조체와 구조체 포인터를 이용하여 스택을 구현함

앞선 예제를 응용하여 정답 코드와 근접한 코드를 구현해낼 수 있었음

정답코드와 다른 점은 init과 pop에서 비어있는 구조체 멤버 data의 요소를 NULL로 초기화 시켜줌

구조체 스택 (정답 코드)

소스코드 위치

#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)--];
}
// 피크함수
element peek(StackType* s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[s->top];
}
// ===== 스택 코드의 끝 ===== 


int main(void)
{
    StackType Stack;
    init_stack(&Stack);
    for (int i = 0; i < 100; i++) {
        push(&Stack, i);
        printf("push [%d] -> %d\n", Stack.top, Stack.data[i]);
    }
    printf("=====================================\n");

    for (int i = 0; i < 100; i++) {
        printf("pop [%d] -> %d\n", Stack.top, pop(&Stack));
    }
}

함수 원형을 참고하여 코드를 작성하였음

peek 함수는 따로 구현되어있지 않은데 pop을 응용하여 쉽게 구현 가능

스택 응용 2

---

동적 배열 스택 (스스로 해보기)

#define _CRT_SECURE_NO_WARNINGS
#define MAX_STACK_SIZE 100

#include <stdio.h>
#include <stdlib.h>
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);
}

int is_full(StackType* s) {
    return (s->top == (MAX_STACK_SIZE - 1));
}

void push(StackType* s, element item) {
    if (is_full(s)) {
        s->capacity *= 2;    //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, "Error - STACK IS EMPTY!");
        exit(-1);
    }
    return s->data[(s->top)--];
}

int main(void) {
    StackType* Stack;
    init_stack(&Stack);

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

    printf("%d \n", pop(&Stack));
    printf("%d \n", pop(&Stack));
    printf("%d \n", pop(&Stack));
    free(Stack->data);

    return 0;
}

동적 배열 스택 (정답 코드)

#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 == (MAX_STACK_SIZE - 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, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}
int main(void)
{
    StackType 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));
    free(s.data);
    return 0;
}

:bulb: 두 코드 모두 마지막에 디버깅 예외로 인하여 오류 후 종료됨.

:bulb: 스스로 작성한 코드의 마지막 free()에는 구조체 요소에 화살표 연산자 (->)로 접근하지 않으면 안되었는데
정답코드는 . 으로 연결하였음.. 두 차이가 궁금함..

느낀점

이론 자체는 어렵지 않은 부분이었으나, 구현하는데 상당히 복잡하게 하였음. 생각을 조금 더 "프로그래머" 적으로 하여 효율적인 코드를 짜도록 노력해야 할 것 같음.