[ch 06-3] 스택의 연결 리스트 기반 구현

[소스 코딩]

■ ListBaseStack.h

#ifndef __LB_STACK_H__
#define __LB_STACK_H__
 
#define TRUE    1
#define FALSE    0
 
typedef int Data;                        // 사용자 정의 int형 Data 선언
 
typedef struct _node                     // 사용자 정의 구조체 'Node' 정의
{
    Data data;                           // 입력 받은 데이터를 저장할 data 선언
    struct _node * next;                 // 다음 노드를 가리킬 노드 포인터 next 선언
} Node;
 
typedef struct _listStack                // 사용자 정의 구조체 'ListStack' 정의
{
    Node * head;                         // ListStack에 노드 포인터 'head' 선언
} ListStack;
 
 
typedef ListStack Stack;                 // ListStack 이름을 'Stack'으로 변경
 
void StackInit(Stack * pstack);          // 스택을 초기화 하는 함수
int SIsEmpty(Stack * pstack);            // 스택에 데이터가 비어있는지 확인하는 함수
 
void SPush(Stack * pstack, Data data);   // 스택에 데이터를 삽입하는 함수
Data SPop(Stack * pstack);               // 스택에서 데이터를 추출하는 함수
Data SPeek(Stack * pstack);              // 스택의 데이터를 확인하는 함수
 
#endif

■ 각 함수의 정의

// 스택을 초기화 하는 함수 //
void StackInit(Stack * pstack)
{
    pstack->head = NULL;
}

- head가 NULL을 가리키게 함

// 스택에 데이터가 비어있는지 확인하는 함수 //
int SIsEmpty(Stack * pstack)
{
    if(pstack->head == NULL)
        return TRUE;
    else
        return FALSE;
}

- head가 NULL이면 TRUE를 반환

- 아니면(=노드를 가리키고 있다면) FALSE를 반환

// 스택에 데이터를 삽입하는 함수 //
void SPush(Stack * pstack, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
 
    newNode->data = data;
    newNode->next = pstack->head;
 
    pstack->head = newNode;
}

- newNode라는 노드를 생성(동적 메모리로 할당)

- 입력 받은 data를 노드 newNode의 data에 저장

- 노드 newNode의 next가 head와 동일한 것을 가리킴

  ※ 최초 시 NULL을 가리키게 됨. 이후 기존 노드의 머리 부분에 추가됨

- head는 newNode를 가리킴

// 스택에서 데이터를 추출하는 함수
Data SPop(Stack * pstack)
{
    Data rdata;
    Node * rnode;
 
    if(SIsEmpty(pstack)) {
        printf("Stack Memory Error!");
        exit(-1);
    }
 
    rdata = pstack->head->data;
    rnode = pstack->head;
 
    pstack->head = pstack->head->next;
    free(rnode);
 
    return rdata;
}

- 삭제할 데이터를 저장할 rdata 선언

- 삭제할 노드를 가리킬 노드 포인터 변수 rnode 선언

- 스택에 데이터가 비워져 있다면(=SIsEmpty 함수를 호출하여 반환된 값이 TRUE면) "Stack Memory Error!"를 출력하고 함수 종료

- rdata에 head가 가리키는 노드의 data를 저장

- rnode가 head가 가리키는 노드를 가리킴

- head가 head의 다음(next) 노드를 가리킴

- rnode가 가리키는 노드를 삭제

- rdata에 저장된 값을 반환

// 스택의 데이터를 확인하는 함수
Data SPeek(Stack * pstack)
{
    if(SIsEmpty(pstack)) {
        printf("Stack Memory Error!");
        exit(-1);
    }
 
    return pstack->head->data;
}

- 데이터가 비워져 있는 상태라면 "Stack Memory Error!"를 출력하고 함수 종료

- head가 가리키는 노드에 저장된 data를 반환

■ ListBaseStack.c

#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"
 
// 스택을 초기화 하는 함수 //
void StackInit(Stack * pstack)
{
    pstack->head = NULL;
}
 
// 스택에 데이터가 비어있는지 확인하는 함수 //
int SIsEmpty(Stack * pstack)
{
    if(pstack->head == NULL)
        return TRUE;
    else
        return FALSE;
}
 
// 스택에 데이터를 삽입하는 함수 //
void SPush(Stack * pstack, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
 
    newNode->data = data;
    newNode->next = pstack->head;
 
    pstack->head = newNode;
}
 
// 스택에서 데이터를 추출하는 함수 //
Data SPop(Stack * pstack)
{
    Data rdata;
    Node * rnode;
 
    if(SIsEmpty(pstack)) {
        printf("Stack Memory Error!");
        exit(-1);
    }
 
    rdata = pstack->head->data;
    rnode = pstack->head;
 
    pstack->head = pstack->head->next;
    free(rnode);
 
    return rdata;
}
 
// 스택의 데이터를 확인하는 함수 //
Data SPeek(Stack * pstack)
{
    if(SIsEmpty(pstack)) {
        printf("Stack Memory Error!");
        exit(-1);
    }
 
    return pstack->head->data;
}

■ ListBaseStackMain.c

#include <stdio.h>
#include "ListBaseStack.h"
 
int main(void)
{
    // Stack의 생성 및 초기화 ///////
    Stack stack;
    StackInit(&stack);
 
    // 데이터 넣기 ///////
    SPush(&stack, 6);  SPush(&stack, 2);
    SPush(&stack, 15);  SPush(&stack, 25);
    SPush(&stack, 1);
 
    // 데이터 조회 ///////
    printf("마지막에 저장된 데이터: %d \n\n", SPeek(&stack));
 
    // 데이터 꺼내기 ///////
    printf("저장된 데이터 출력: ");
    while(!SIsEmpty(&stack))
        printf("%d ", SPop(&stack)); 
 
    return 0;
}

- 노드 생성 및 데이터 삽입 순서(6 → 2 → 15 → 25 → 1)

- 마지막에 저장된 데이터 조회: SPeek(&stack) 함수 호출

- 저장된 데이터 출력: SIsEmpty 함수를 호출하여 반환된 값이 'TRUE가 아니면'(=FALSE) SPop 함수 호출 반복

■ 실행결과

■ 연결 리스트 그림