5.4.2 스택 구현

스택 구현은 큐 구현과 매우 흡사합니다. 먼저 동적으로 스택을 생성하는 함수와 소멸하는 함수는 큐 구현처럼 래퍼 함수로 구현합니다.

EHStack *New_EHStack()
{
    return New_LinkedList();
}
void Delete_EHStack(EHStack *ehs)
{
    Delete_LinkedList(ehs);
}

스택에 자료를 보관하는 함수도 연결리스트에 순차 보관하는 함수를 호출하는 래퍼 함수입니다.

void EHStack_Push(EHStack *ehs, Element data)
{
    LinkedList_PushBack(ehs,data);
}

스택에서 가장 최근에 보관한 자료를 꺼내는 함수를 작성합시다. 이 부분이 큐와 차이가 있는 부분입니다.

Element EHStack_Pop(EHStack *ehs)
{
    Element element = 0;

스택이 비어있지 않을 때 가장 최근에 보관한 자료를 꺼내야 합니다.

    if( ! EHStack_IsEmpty(ehs))
    {

연결리스트에서는 마지막 보관한 자료의 다음 노드를 얻어오는 함수가 있습니다. 이를 통해 얻어온 링크는 더미 노드인 tail 정보이며 이 노드의 이전 노드가 가장 최근에(가장 뒤에) 보관한 자료를 가진 노드의 위치 정보입니다.

        Link last = LinkedList_End(ehs);
        last = last->prev;

이제 해당 노드의 자료를 반환할 element 변수에 설정하고 해당 위치의 노드를 연결리스트에서 제거합니다.

        element = last->data;
        LinkedList_Erase(ehs,last);
    }

element를 반환합니다.

    return element;
}

스택이 비었는지 확인하는 함수는 큐의 구현처럼 usage값이 0인지 확인한 값을 반환합니다.

int EHStack_IsEmpty(EHStack *ehs)
{
    return ehs->usage == 0;
}

다음은 EHStack.c 파일의 내용입니다.

//EHStack.h
#include "EHStack.h"
EHStack *New_EHStack()
{
    return New_LinkedList();	
}
void Delete_EHStack(EHStack *ehs)
{
    Delete_LinkedList(ehs);	
}
void EHStack_Push(EHStack *ehs, Element data)
{
    LinkedList_PushBack(ehs,data);
}
Element EHStack_Pop(EHStack *ehs)
{
    Element element = 0;
    if( ! EHStack_IsEmpty(ehs))
    {
        Link last = LinkedList_End(ehs);
        last = last->prev;
        element = last->data;
        LinkedList_Erase(ehs,last);
    }
    return element;
}
int EHStack_IsEmpty(EHStack *ehs)
{
    return ehs->usage == 0;    
}