linked list를 이용해 스택을 구현해 보자.

헤더 분석

#ifndef _LINKED_STACK_
#define _LINKED_STACK_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct StackNodeType
{
	char data;
	struct StackNodeType* pLink;
} StackNode;

typedef struct LinkedStackType
{
	int currentElementCount;	// 현재 스택의 원소 개수
	StackNode* pTopElement;		// Top 노드의 주소 저장. 헤더 따로 없음
} LinkedStack;

LinkedStack* createLinkedStack();
int pushLS(LinkedStack* pStack, StackNode element);
StackNode* popLS(LinkedStack* pStack);
StackNode* peekLS(LinkedStack* pStack);
void deleteLinkedStack(LinkedStack* pStack);
int isLinkedStackFull(LinkedStack* pStack);
int isLinkedStackEmpty(LinkedStack* pStack);

#endif

#ifndef _COMMON_STACK_DEF_
#define _COMMON_STACK_DEF_

#define TRUE		1
#define FALSE		0
#define ERROR		-1

#endif

이전의 Linked List 구현에서는 LikedList 구조체에 headerNode라는 노드를 두었는데, 이번에는 LinkedStack 구조체에 pTopElement라는 노드 포인터를 두었다. 헤더 노드가 없고, 바로 0부터 이어지는 것이 LinkedList를 이용한 stack구현의 핵심인 것 같다. 이 부분에 유의하자.

Untitled

노드 부분은 LinkedList와 비슷하다. data가 char형식인 것만 빼면 다음 노드를 가리키는 주소값이 구조체 속 멤버변수로 포함된 것이 같다.

NULL과 memset을 이용하기 위한 string.h 헤더와 printf를 이용하기 위한 stdio.h헤더, malloc을 이용하기 위한 stdlib.h헤더를 include해 주었다.

또한 linked list는 array list와는 다르게 초기에 원소 개수를 지정해 놓지 않고 계속 원소 개수가 늘어날 수 있기 때문에 arrayStack 구현과 달리 maxElementCount가 지정되어 있지 않다.

createLinkedStack 함수 구현

LinkedStack* createLinkedStack()
{
  	LinkedStack* pStack = NULL;
    pStack = (LinkedStack*)malloc(sizeof(LinkedStack));
    if (pStack == NULL)
    {
        printf("[error] malloc failure : pStack\\n");
        return (NULL);
    }
    memset(pStack, 0, sizeof(LinkedStack));
    return (pStack);
}

함수 기능 : LinkedStack을 malloc하고 그 주소값을 반환하는 함수.

pushLS 함수 구현

int		pushLS(LinkedStack* pStack, StackNode element)
{
  	StackNode *pNode = NULL;
  	if (pStack == NULL)
    {
      	printf("[error] Null parameter : pStack\\n");//pStack이 NULL인 상태
      	return (FALSE);
    }
  	pNode = (StackNode*)malloc(sizeof(StackNode));//pNode를 동적 할당.
  	if (pNode == NULL)//동적 할당 실패 시
    {
      	printf("[error] malloc failure : pNode\\n");
        return (FALSE);
    }
  	*pNode = element;//pNode의 값을 element로 바꿈.
  	pNode->pLink = pStack->pTopElement;//newElement의 pLink는 topElement의 주소값.
  	pStack->pTopElement = pNode;//0번째 노드가 추가되었으니 이제 새로운 topElement는 새로 추가된 노드.
  	pStack->currentElementCount++;
    return (TRUE);
} // maxElementCount가 없음.
// pTopElement 자체가 0번째 노드

함수 기능 : element 노드를 인자로 전달받아 pStack에 push하는 함수.