[C언어] 링크드 리스트로 구현한 int 저장형 스택 예제

Luyin 2012. 8. 6. 03:50

LinkedListStack.h

#ifndef LINKEDLIST_STACK_H 
#define LINKEDLIST_STACK_H 

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

typedef struct tagNode 
{ 
    int Data; 
    struct tagNode * NextNode; 
} Node; 

typedef struct tagLinkedListStack
{ 
    Node * List; 
    Node * Top; 
} LinkedListStack; 

void LLS_CreateStack (LinkedListStack ** Stack); 
void LLS_DestroyStack (LinkedListStack * Stack); 

Node* LLS_CreateNode (int * Data); 
void LLS_DestroyNode( Node* _Node ); 

void LLS_Push (LinkedListStack* Stack, Node* NewNode); 
Node * LLS_Pop(LinkedListStack* Stack); 

Node * LLS_Top( LinkedListStack* Stack); 
int LLS_GetSize( LinkedListStack* Stack); 
int LLS_IsEmpty( LinkedListStack* Stack); 

#endif

LinkedListStack.c

#include "LinkedListStack.h" 

void LLS_CreateStack( LinkedListStack** Stack) 
{ 
    /* 스택을 자유 저장소에 생성 */ 
    (*Stack) = (LinkedListStack*)malloc(sizeof (LinkedListStack));
    (*Stack)->List = NULL; 
    (*Stack)->Top = NULL; 
} 

void LLS_DestroyStack(LinkedListStack* Stack) 
{ 
    while( !LLS_IsEmpty(Stack) ) 
    { 
        Node * Popped = LLS_Pop( Stack ); 
        LLS_DestroyNode(Popped); 
    } 

    /* 스택을 자유 저장소에서 해제 */ 
    free(Stack); 
} 

Node * LLS_CreateNode (int * NewData) 
{ 
    Node * NewNode = (Node*)malloc(sizeof(Node)); 
     
    NewNode->Data = *NewData; /* 데이터를 저장한다. */ 

    NewNode->NextNode = NULL;    /* 다음 노드에 대한 포인터는 NULL로 초기화한다. */ 

    return NewNode; /* 노드의 주소를 반환한다. */ 
} 

void LLS_DestroyNode( Node* _Node ) 
{ 
    free(_Node); 
} 

void LLS_Push( LinkedListStack* Stack, Node* NewNode ) 
{ 
    if( Stack->List == NULL) 
    { 
        Stack->List = NewNode; 
    } 
    else 
    { 
        /* 최상위 노드를 찾아 NewNode를 연결한다 (쌓는다).        */ 
        Node * OldTop = Stack->List; 
        while( OldTop->NextNode != NULL) 
        { 
            OldTop = OldTop->NextNode; 
        } 

        OldTop->NextNode = NewNode; 
    } 

    /* 스택의 Top 필드에 새 노드의 주소를 등록한다. */ 
    Stack->Top = NewNode; 
} 

Node* LLS_Pop( LinkedListStack* Stack) 
{ 
    /* LLS_Pop() 함수가 반환할 최상위 노드 */ 
    Node* TopNode = Stack->Top; 

    if( Stack->List == Stack->Top) 
    { 
        Stack->List = NULL; 
        Stack->Top = NULL; 
    } 
    else 
    { 
        /* 새로운 최상위 노드를 스택의 Top 필드에 등록한다. */ 
        Node* CurrentTop = Stack->List; 
        while( CurrentTop != NULL && CurrentTop->NextNode != Stack->Top) 
        { 
            CurrentTop = CurrentTop->NextNode; 
        } 
        Stack->Top = CurrentTop; 
        CurrentTop->NextNode = NULL; 
    } 

    return TopNode; 
} 

Node * LLS_Top( LinkedListStack* Stack) 
{ 
    return Stack->Top; 
} 

int LLS_GetSize ( LinkedListStack* Stack) 
{ 
    int Count = 0; 
    Node * Current = Stack->List; 

    while( Current != NULL)
    { 
        Current = Current->NextNode; 
        Count++; 
    } 

    return Count; 
} 

int LLS_IsEmpty( LinkedListStack* Stack) 
{ 
    return (Stack->List == NULL); 
}

Test_LinkedListStack.c

int main(void)
{
	int i=0;
	int Count =0;
	Node* Popped;

	LinkedListStack* Stack;
	LLS_CreateStack(&Stack);

	LLS_Push(Stack,LLS_CreateNode("abc"));
	LLS_Push(Stack,LLS_CreateNode("def"));
	LLS_Push(Stack,LLS_CreateNode("efg"));
	LLS_Push(Stack,LLS_CreateNode("hij"));

	Count = LLS_GetSize(Stack);
	printf("Size : %d, Top : %s\n\n",Count,LLS_Top(Stack)->Data);

	for(i=0; i<count; {="" ?,popped-="" %s,="" printf(?popped:="" popped="LLS_Pop(Stack);" break;="" if(lls_isempty(stack))="" i++)="">Data);
		}
		else
		{
			printf("Stack is Empty.\n");
		}
	}
	LLS_DestroyStack(Stack);
	getchar();
	return 0;
}

'뇌를 자극하는 알고리즘' 의 스택 부분을 그대로 복사하여 int형에 맞게 수정한 것입니다.