언어 자료구조 알고리즘/디딤돌 자료구조 (C언어)

[C언어 자료구조] 5.2 스택 구현

언제나휴일 2016. 11. 26. 13:11
반응형

[C언어 자료구조] 5.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;

}

 

반응형