스택(Stack)

: 쌓다, 더미

: LIFO(Last In First Out) 형식의 자료구조

책이 쌓여있는 것이나 프링글스 통을 생각하자. 이것은 한쪽에서만 자료를 넣고 뺄 수 있다. 가장 최근에 넣은 것을 가장 먼저 빼낼 수 있다

---

스택의 연산

• int Top()
  : 스택의 가장 윗 데이터를 반환
  만약 스택이 비었다면 이 연산은 정의불가 상태

• int full()
  : 스택이 꽉 차있는지 검사
  top 변수가 (스택사이즈 - 1)과 같다면 꽉 찬 것
  꽉 차있으면 1 반환, 그렇지 않다면 0 반환

• int empty()
  : 스택이 비어있는지 검사
  top 변수가 -1을 갖으면 비어있음
  비어있으면 1 반환, 그렇지 않다면 0 반환

• void push()
  : 스택이 꽉 차있는지 검사하고, 그렇지 않다면 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, data 넣음
  만약 스택이 꽉 차있는 경우에는 스택오버플로우(stack overflow)

• int pop()
  : 스택이 비어있는지 검사하고, 그렇지 않다면 스택의 가장 윗 데이터를 반환하고 삭제
  스택이 비었다면 연산 정의불가 상태

• void printStack()
  : 스택의 모든 원소 출력
  아래에서부터 위까지

---

스택의 구현

+) 1주차 과제 조건
동적 메모리할당과 구조체를 이용해서 스택과 큐 구현하기
스택(큐)에 원소 추가, 삭제하는 기능이 있어야 함
스택(큐)에 할당된 메모리 이상으로 원소가 추가 될 때 메모리 확장도 구현해야함
메모리 할당 해제도 구현해야 함

---

소스코드

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

typedef struct stack
{
    int top;
    int *data;
    int max;
}stack;

void initStack(stack *S, int size)
{
    S->data = (int *) malloc(size * sizeof(int));
    S->top = -1;
    S->max = size;
}

int Top(stack *S)
{
    if (S->top != -1)
        return (S->data[S->top]);
}

int full(stack *S)
{
    if (S->top == S->max - 1)
        return (1);
    return (0);
}

int empty(stack *S)
{
    if (S->top == -1)
        return (1);
    return (0);
}

void push(stack *S, int data)
{
    if (!full(S))
    {
        S->top++;
        S->data[S->top] = data;
    }
    else
    {
        S->data = (int *) realloc(S->data, S->max * 2 * sizeof(int));
        push(S, data);
    }
}

int pop(stack *S)
{
    int value;

    if (!empty(S))
    {
        value = S->data[S->top];
        S->top--;
        return (value);
    }
    return (0);
}

void printStack(stack *S)
{
    if (!empty(S))
    {
        int i;

        i = 0;
        while (i <= S->top)
        {
            printf("%d", S->data[i]);
            if(i != S->top)
                printf(", ");
            i++;
        }
    }
}

---

백준 10828

https://www.acmicpc.net/problem/10828

이 문제 메인에서
stack *s로 선언하고 화살표 연산자로 접근하면 런타임 에러 (AccessNullPointer)가 난다...
(로컬에서는 잘 돌아간다)
stack s로 선언하고 도트 연산자로 접근해서는 통과했다

-> 어떤 분이 질문하고 답변한 글을 보았는데,
https://www.acmicpc.net/board/view/72505
https://www.acmicpc.net/board/view/21284
스택이 비어있으면 top을 호출 할 수 없고
처음에 s가 널로 초기화 되어있으면 s포인터는 사용할 수 없고
이런 문제 때문에 런타임 에러가 날 수 있다고 한다..

알고보니 선언을 하고 난 뒤 초기화를 해줄 때 넣은 친구도 또 초기화를 해줘야되는 상황이었다

s = (stack *) malloc(sizeof(stack));

으로 해결함!

Wall Wextra Werror 옵션을 생활화 하자