이번에는 array list로 스택을 구현해 본다.

헤더 분석

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

typedef struct ArrayStackNodeType {
	char data;
} ArrayStackNode;

typedef struct ArrayStackType {
	int maxElementCount;		// �ִ� ���� ����
	int currentElementCount;	// ���� ������ ����
	ArrayStackNode *pElement;	// ��� ������ ���� 1���� array
} ArrayStack;

ArrayStack* createArrayStack(int maxElementCount);
int pushAS(ArrayStack* pStack, ArrayStackNode element);
ArrayStackNode* popAS(ArrayStack* pStack);
ArrayStackNode* peekAS(ArrayStack* pStack);
void deleteArrayStack(ArrayStack* pStack);
int isArrayStackFull(ArrayStack* pStack);
int isArrayStackEmpty(ArrayStack* pStack);

#endif

#ifndef _COMMON_STACK_DEF_
#define _COMMON_STACK_DEF_

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

#endif

헤더에서 구조체 부분은 data의 형식이 char형인 것만 빼면 array list와 구조가 같다. ArrayStack 구조체에서 maxElementCount는 최대 원소 개수, currentElementCount는 현재 원소 개수를 의미하고, pElement는 0번째 노드의 주소를 가리킨다.

• 이 ArrayStack 또한 인덱스의 주소가 연속되어 있어 인덱스만으로도 충분히 노드의 주소를 알아낼 수 있다.
• 단 LinkedList의 경우에는 노드의 주소가 연속되어 있지 않아 순회해서 노드를 찾아가야 한다.
• top은 배열의 마지막 원소(currentElementCount - 1번지)를 가리키는데, 이것이 linked list로 구현한 스택과의 가장 큰 차이점이다. 링크드 리스트의 경우, top은 0번째 노드가 되며 이는 노드가 이어진 순서와는 반대라는 것을 알아챌 수 있다.
• pop, push, peek을 할 때, currentElementCount - 1번지 원소를 이용하면 된다.
• 또, linked list로 스택을 구현한 것과는 다르게 underflow와 overflow모두를 고려해야 한다. linked list때는 overflow는 고려하지 않고, underflow만 isLinkedStackEmpty함수를 이용해 고려해 주었다.

createArrayStack 함수 구현

ArrayStack* createArrayStack(int maxElementCount)
{
    ArrayStack* pStack = NULL;

    if (maxElementCount < 0)//invalid maxElementCount value
    {
        printf("[error] invalid value : maxElementCount\\n");
        return (pStack);
    }
    pStack = (ArrayStack*)malloc(sizeof(ArrayStack));//스택을 동적할당
    if (pStack == NULL)//동적할당 실패 시
    {
        printf("[error] malloc failure : pStack\\n");
      	return (pStack);
    }
    memset(pStack, 0, sizeof(ArrayStack));//ArrayStack만큼 0으로 초기화
  	pStack->maxElementCount = maxElementCount;//maxElementCount만 값 넣기
  	pStack->pElement = (ArrayStackNode*)malloc(sizeof(ArrayStackNode));//pElement 동적할당
  	if (pStack->pElement == NULL)//pElement 동적할당 실패
    {
      	printf("[error] malloc failure : pElement\\n");
      	free(pStack);
      	return (NULL);
    }
  	memset(pStack->pElement, 0, sizeof(ArrayStackNode) * maxElementCount);//pElement만큼 0으로 초기화
  	return (pStack);
}

함수 기능 : 스택을 동적 할당하여 그 주소값을 반환하는 함수. maxElementCount가 음수인지, pStack에 할당이 잘못된 경우, pStack의 pElement가 할당이 잘못된 경우, 이 3가지의 예외처리를 해 주어야 한다.

< 함수의 구현 순서 >

(1) maxElement가 음수인지 확인하고, 음수라면 NULL 반환

(2) pStack에 ArrayStack만큼의 메모리를 동적 할당하되, 할당 실패 시 NULL 반환

(3) pStack의 모든 값들(구조체 내의 멤버변수들)을 0으로 초기화한 후 maxElementCount값만 인수로 전달받은 값으로 초기화

(4) pElement도 (ArrayStackNode * maxElementCount)만큼의 메모리를 할당하되, 할당 실패시 pStack도 free하고 NULL반환

(5) pElement의 모든 값들(구조체 내의 멤버변수들)을 0으로 초기화한 후 pStack 반환.