[자료구조][C] 스택(stack) (1)

📌 스택이란 ?

스택은 팬케이크 더미를 떠올리면 이해하기 쉽다. 일반적으로 팬케이크를 쌓는 방향은 아래에서 위이다. 그러나 팬케이크를 먹을 때 우리는 쌓여진 맨 위의 펜케이크부터 먹게된다. 스택도 동일하다. Last In First Out (LIFO), 후입선출의 구조로 가장 나중에 들어간 원소가 가장 먼저 나오게 된다.   

LIFO 방식

📌 스택의 연산

• pop(): 스택에서 가장 위에 있는 항목을 제거한다. 
• push(data): data를 스택의 가장 윗 부분에 추가한다.
• peek(): 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty(): 스택이 비어 있는 경우 true를 반환한다. 

📌 스택 연산 코드 

 

creatStack 함수 : 스택을 생성하는 함수 

parameter : 스택관리 구조체의 주소, 스택의 크기 

성공하면 True를, 실패하면 False를 리턴한다. 

BOOL createStack(Stack* sp, int size) {
    if (sp == NULL) return FALSE; // sp포인터가 NULL인지 확인
    sp->stack = (int*)malloc(size,sizeof(int)); //stack 동적할당
    if (sp->stack != NULL){ 
    	 sp->size = size;
         sp->top = 0; // top을 0으로 초기화
         return TRUE;
   }
}

---

isStackFull 함수 : 스택이 꽉 차있는지 확인하는 역할 

parameter : 스택관리 구조체의 주소, 

성공하면 True를, 실패하면 False를 리턴한다. 

BOOL isStackFull(Stack* sp)
{
	if (sp == NULL) { //sp 포인터 NULL check !
		return FALSE;
	}
	if (sp->top == sp->size)
		return TRUE;
	else
		return FALSE;

여기서 top이 size와 같다는 말은 stack이 가득 찼다는 말과 동일하다 !

( 스택의 그림을 생각해봤을때 가장 윗부분인 top의 값이 size와 같다는 것이니 

---

isStackEmpty 함수: 스택이 비었는지 확인해주는 함수

BOOL isStackEmpty(Stack* sp)
{
	if (sp == NULL) { //sp 포인터 NULL CHECK
		return FALSE;
	}
	if (sp->top == 0) {
		return TRUE;
	else
		return FALSE;
	}
}

top이 0이란 말은 아예 아무런 값이 없는 상태 !

---

Function name : push - 스택에 데이터 하나를 저장함
Parameters : sp - 스택관리 구조체의 주소
inData - 스택에 저장할 데이터
Returns : 성공적으로 저장하면 TRUE, 실패하면 FALSE 리턴

BOOL push(Stack* sp, int inData)
{
	if (sp == NULL) //sp포인터 NULL 체크
		return FALSE;
	if (isStackFull(sp)) { //stack() 꽉 차있으면
		return FALSE;
	}
	else {
		sp->stack[sp->top] = inData; //데이터를 top 위치에 저장한 후 top 증가
		sp->top++;
		return TRUE;
	}
}

---

Function name : pop - 스택에서 데이터 하나를 꺼냄
Parameters : sp - 스택관리 구조체의 주소
popData -  꺼낸 데이터를 저장할 기억공간의 주소
Returns : 성공적으로 꺼내면 TRUE, 실패하면 FALSE 리턴

 

BOOL pop(Stack* sp, int* popData)
{
	if (sp == NULL)
		return FALSE;
	if (isStackEmpty(sp)) { //stack이 비어있으면
		return FALSE;
	}   
	else {
		--sp->top;
		*popData = sp->stack[sp->top];
		return TRUE;
	}
}

여기서 sp-> -- top 을 못하는 이유는 연산자 우선순위 때문이다. 

---

Function name : printStack - 스택의 모든 데이터 출력(pop하면 나오는 순서대로 출력)
Parameters : sp - 스택관리 구조체의 주소
Returns : 없음

void printStack(const Stack* sp)
{
	int i = sp->top; // top을 변하지 않기 위해서 i 변수 생성
	if (sp == NULL)         
		return;
	while (i != 0)
	{
		printf("%5d\n", sp->stack[--i]);
	}
	printf("\n");
}

---

Function name : destroyStack -  스택 소멸 함수
Parameters : sp - 스택관리 구조체의 주소
Returns : 없음

void destroyStack(Stack* sp)
{
	if (sp == NULL)
		return;
	if (sp->stack != NULL) {
		free(sp->stack);
	}
	sp->stack = NULL;
	sp->size = 0;
	sp->top = 0;
}

동적할당 해준거 free 하는거 잊지말기 !

---

 

🎀 전체코드  

#include <stdio.h>
#include <malloc.h>

typedef int BOOL;
#define TRUE 1
#define FALSE 0

typedef struct {
    int* stack; // 스택 배열의 주소
    int size;   // 스택의 크기
    int top;    // 스택의 top
} Stack;

BOOL createStack(Stack* sp, int size) {
    if (sp == NULL) return FALSE;
    sp->stack = (int*)malloc(size * sizeof(int));
   if (sp->stack != NULL) {
		sp->size = size;
		sp->top = 0;
	}
    return TRUE;
}

BOOL isStackFull(Stack* sp) {
    if (sp == NULL) return FALSE;
    if (sp->top == sp->size) return TRUE;
    return FALSE;
}

BOOL isStackEmpty(Stack* sp) {
    if (sp == NULL) return FALSE;
    if (sp->top == 0) return TRUE;
    return FALSE;
}

BOOL push(Stack* sp, int inData) {
    if (sp == NULL) return FALSE;
    if (isStackFull(sp)) return FALSE;
    sp->stack[sp->top] = inData;
    sp->top++;
    return TRUE;
}

BOOL pop(Stack* sp, int* popData) {
    if (sp == NULL) return FALSE;
    if (isStackEmpty(sp)) return FALSE;
    sp->top--;
    *popData = sp->stack[sp->top];
    return TRUE;
}

void printStack(const Stack* sp) {
    if (sp == NULL) return;
    for (int i = sp->top - 1; i >= 0; i--) {
        printf("%5d\n", sp->stack[i]);
    }
    printf("\n");
}

void destroyStack(Stack* sp) {
    if (sp == NULL) return;
    if (sp->stack != NULL) free(sp->stack);
    sp->stack = NULL;
    sp->size = 0;
    sp->top = 0;
}