[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;

}