[C언어 소스] 스택을 연결리스트로 구현

안녕하세요. 언제나 휴일입니다.

이번에는 스택(STACK)을 연결리스트로 구현하는 소스 코드입니다.

스택은 자료를 한쪽으로 보관하고 꺼내는 LIFO(Last In First Out) 방식의 자료구조입니다. 스택에 자료를 보관하는 연산을 PUSH라 말하고 꺼내는 연산을 POP이라고 말합니다. 그리고 가장 최근에 보관한 위치 정보를 TOP 혹은 스택 포인터라 말합니다.

알고리즘

Push 연산
IF Top> MAX Then (꽉 차면)
    Overflow (버퍼 오버플로우)
Else (꽉 차지 않을 때)
    Top = Top +1 (Top 위치를 1 증가)
    Buffer[Top] = data (버퍼의 Top 위치에 data 보관)

Pop 연산
IF Top=-1 Then (비었으면)
    Underflow (버퍼 언더플로우)
Else
    data = Buffer[Top] (버퍼의 Top 위치의 값을 데이터에 설정)
    Top = Top -1  (Top 위치를 1 감소)

스택 실행 결과
스택 실행 결과

소스 코드

//스택 - 연결리스트로 구현
#include <stdio.h>
#include <stdlib.h>


typedef struct Node //노드 정의
{
    int data;
    struct Node *next;
}Node;

typedef struct Stack //Stack 구조체 정의
{
    Node *top;    //맨 앞 노드(가장 최근에 생성한 노드)
}Stack;

void InitStack(Stack *stack);//스택 초기화
int IsEmpty(Stack *stack); //스택이 비었는지 확인
void Push(Stack *stack, int data); //스택에 보관
int Pop(Stack *stack); //스택에서 꺼냄

int main(void)
{
    int i;
    Stack stack;

    InitStack(&stack);//스택 초기화
    for (i = 1; i <= 5; i++)//1~5까지 스택에 보관
    {
        Push(&stack, i);
    }
    while (!IsEmpty(&stack))//스택이 비어있지 않다면 반복
    {
        printf("%d ", Pop(&stack));//스택에서 꺼내온 값 출력
    }
    printf("\n");
    return 0;
}
void InitStack(Stack *stack)
{
    stack->top = NULL; //스택 초기화에서는 top을 NULL로 설정
}

int IsEmpty(Stack *stack)
{
    return stack->top == NULL;    //top이 NULL이면 빈 상태    
}
void Push(Stack *stack, int data)
{
    Node *now = (Node *)malloc(sizeof(Node)); //노드 생성
    now->data = data;//데이터 설정
    now->next = stack->top;//now의 next링크를 현재 top으로 설정   
    stack->top = now;   //스택의 맨 앞은 now로 설정
}
int Pop(Stack *stack)
{
    Node *now;
    int re;
    if (IsEmpty(stack))
    {
        return 0;
    }
    now = stack->top;//now를 top으로 설정
    re = now->data;//꺼낼 값은 now의 data로 설정

    stack->top = now->next;//top을 now의 next로 설정
    free(now);//필요없으니 메모리 해제
    return re;
}