C 스택(Stack) 구현

스택

- 선형 자료구조의 일종이다.

- 들어간 것이 먼저 나오는 후입선출(LIFO : Last In First Out)형식의 자료구조이다.

  ※ 사용 예로 브라우저의 뒤로가기 기능을 들 수 있다.

 

  ※ 위의 그림 기준으로 입력의 순서는 A → D → C, 출력은 C → D → A 순으로 이루어진다.

 

그럼 본격적으로 코드를 작성하기 전 활용할 구조체는 다음과 같다.

typedef struct Stack
{
    int data;
    struct Stack* NEXT;
}Stack;

 

 

Push (입력)

Stack* Push(Stack* node, int data)
{
    Stack* newNode = (Stack*)malloc(sizeof(Stack));
    newNode->data = data;
    newNode->NEXT = node;
	
    return newNode;
}

  ※ 새로 할당한 노드의 자기참조 변수는 앞에 만들어진 노드(인수로 받은 노드)를 대입하면 된다.

 

 

Pop(출력)

Stack* Pop(Stack* node)
{
    if (node == NULL) return NULL;
	
    Stack* deleteNode = node;
    node = node->NEXT;
    free(deleteNode);
	
    return node;
}

  ※ 현재(Top)의 노드를 할당해제하고 인수로 받은 노드의 다음 노드를 반환한다.

 

위 과정을 그림으로 풀면 다음과 같다.

  ※ 제일 마지막에 Push된 데이터가 스택의 Top이 된다.

  ※ Push :  현재 Top(Stack3)을 인수로 넘겨주면 Push함수에서 노드를 동적할당하고 Stack->NEXT에 인수로 받은 Stack3을 대입해주고 반환해주면, Top은 새로 할당한 노드로 변경이 되고 기존 노드(Stack3)은 새로 할당한 노드의 참조 변수(NEXT)에 대입해주면 된다.

  ※ Pop : 현재 Top을 인수로 넘겨주면 되고, Pop함수에서 인수로 받은 Top 노드를 할당 해제 해주고, Top노드의 참조 변수(NEXT)를 반환해주면 된다.

 

 

풀 소스코드는 다음과 같다.

#include <stdio.h>
#define MAX 10

typedef struct Stack
{
    int data;
    struct Stack* NEXT;
}Stack;

Stack* Push(Stack* node, int data)
{
    Stack* newNode = (Stack*)malloc(sizeof(Stack));
    newNode->data = data;
    newNode->NEXT = node;
	
    return newNode;
}

Stack* Pop(Stack* node)
{
    if (node == NULL)
    {
        printf("데이터가 없습니다.\n");
        return NULL;
    }
	
    printf("%d ", node->n);
    Stack* deleteNode = node;
    node = node->NEXT;
    free(deleteNode);
	
    return node;
}

void main()
{
    Stack* top = NULL;
    for(int i = 0; i < MAX; i++)
        top = Push(top, data);
    
    //현재 상태 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9(top)
    
    for(int i = 0; i < MAX; i++)
    	top = Pop(top);
        
    //결과 : 9 8 7 6 5 4 3 2 1 0
}