[Data Structure] 6. Array Stack

특징

1. 후입선출 (LIFO: Last-In-First-Out)

• 가장 나중에 들어온 자료가 먼저 pop 됨

2. 선형 자료구조

개념

1. 탑: 가장 최근에 스택에 삽입된 자료
   

2. 스택의 3가지 연산

   2-1. PUSH(푸시)
   

   • Overflow 현상이 발생할 수 있음

   2-2. POP(팝)
   

   • Underflow 현상이 발생할 수 있음

   2-3. PEEK(피크)
   

   • 스택의 맨 위에 있는 원소(top)를 반환
   • pop처럼 스택에서 원소를 제거하거나 하지는 않음

구현

1. arraystack.c

#include "arraystack.h"

ArrayStack* createArrayStack(int maxElementCount)
{
	ArrayStack *new;

	new = malloc(sizeof(ArrayStack) * 1); // arraystack 할당
	if (!new) 
		return (NULL);
	new->maxElementCount = maxElementCount; // 최대 원소 개수 설정
	new->currentElementCount = 0; // 현재 원소 개수 초기화
	new->pElement = malloc(sizeof(ArrayStackNode) * maxElementCount); // 원소 저장을 위한 배열 포인터 최대 원소 개수 크기만큼 할당
	if (!(new->pElement)) // 배열 할당 실패 시
	{
		free(new); // arraystack free
		return (NULL);
	}
	return (new);
}

int pushAS(ArrayStack* pStack, ArrayStackNode element)
{
	ArrayStackNode *newElement;

	if(!pStack) // 예외처리
		return (FALSE);
	if (pStack->currentElementCount == pStack->maxElementCount) // 배열이 꽉 찼을 경우 새 배열 할당
	{
		printf("Array is Full. New Array Allocated. Size of Array : %d\n", pStack->maxElementCount * 2);
		newElement = malloc(sizeof(ArrayStackNode) * (pStack->maxElementCount * 2)); // 현재 배열의 2배 크기 배열 할당
		if (!newElement)
			return (FALSE); 
		pStack->maxElementCount *= 2; // 최대 원소 개수 재설정
		for (int i = 0; i < pStack->currentElementCount; i++) // 새 배열에 이전 배열 정보 복사
			newElement[i] = pStack->pElement[i];
		free(pStack->pElement); // 이전 배열 free
		pStack->pElement = newElement; // 스택 배열 포인터에 새 배열 연결
	}
	pStack->pElement[pStack->currentElementCount] = element; // 배열 마지막 인덱스에 추가 할 요소 삽입
	pStack->currentElementCount++; // 현재 원소 개수 갱신
	return (TRUE);
}

ArrayStackNode* popAS(ArrayStack* pStack)
{
	if ((!pStack) || pStack->currentElementCount == 0) // 에러 처리
		return (NULL);
	pStack->currentElementCount--; // 현재 원소 개수 갱신
	return (&pStack->pElement[pStack->currentElementCount]); // 0부터 시작하는 배열 인덱싱에 따라 현재 원소 개수를 갱신한 후 해당 인덱스에 접근 시 기존 top 원소를 반환 할 수 있음
}

ArrayStackNode* peekAS(ArrayStack* pStack)
{
	if ((!pStack) || pStack->currentElementCount == 0) // 에러 처리
		return (NULL);
	return (&pStack->pElement[pStack->currentElementCount - 1]); // 현재 원소 개수는 변하지 않으며 현재 top 원소 반환
}

void displayStack(ArrayStack *pStack)
{
	if (!pStack) // 에러 처리
	{
		printf("No Array\n\n");
		return ;
	}
	printf("(1) Size of Array: %d\n", pStack->maxElementCount);
	printf("(2) Current Element count: %d\n", pStack->currentElementCount);
	if (pStack->currentElementCount == 0)
		printf("(3) Element: No Element");
	else
		printf("(3) Element:\n");
	for (int i = 0; i < pStack->currentElementCount; i++)
	{
		printf("[%d] = %c", i, pStack->pElement[i].data);
		if (i != pStack->currentElementCount - 1)
			printf(", ");
	}
	printf("\n\n");
}

int isArrayStackFull(ArrayStack* pStack)
{
	return (pStack->currentElementCount == pStack->maxElementCount);
}

int isArrayStackEmpty(ArrayStack* pStack)
{
	return (pStack->currentElementCount == 0);
}

void deleteArrayStack(ArrayStack* pStack)
{
	if (!pStack)
		return ;
	free(pStack->pElement); // 배열 포인터 free
	pStack->pElement = NULL;
	free(pStack); // 스택 free
}

2. arraystack_main.c

#include "arraystack.h"

int main(void)
{
	ArrayStack	*pStack;
	ArrayStackNode	*element;
	ArrayStackNode	stackElement;
	int				loop;
	int				opt;

	pStack = NULL;
	opt = 0;
	while (loop)
	{
		printf("[1] Create [2] Push [3] Pop [4] Peek [5] Check Full [6] Check Empty [7] Display [8] Delete [9] Exit ");
		scanf("%d", &opt);
		switch (opt)
		{
			case 1:
				if (pStack)
				{
					printf("Stack already exists.\n\n");
					break;
				}
				printf("Size of Array: ");
				scanf("%d", &opt);
				pStack = createArrayStack(opt);
				if (pStack)
					printf("Create Array: Success\n\n");
				else
					printf("Create Array: Failed\n\n");
				break;
			case 2:
				printf("Data: ");
				scanf(" %c", &stackElement.data);
				if (pushAS(pStack, stackElement))
				{
					printf("Push: Success\n\n");
					displayStack(pStack);
				}
				else
					printf("Push: Failed\n\n");
				break;
			case 3:
				element = popAS(pStack);
				if (element)
				{
					printf("Pop: %c\n", element->data);
					displayStack(pStack);
				}
				else
					printf("Pop: Failed\n\n");
				break;
			case 4:
				element = peekAS(pStack);
				if (element)
					printf("Peek: %c\n\n", element->data);
				else
					printf("Peek: Failed\n\n");
				break;
			case 5:
				if (isArrayStackFull(pStack))
					printf("Yes\n\n");
				else
					printf("No\n\n");
				break;
			case 6:
				if (isArrayStackEmpty(pStack))
					printf("Yes\n\n");
				else
					printf("No\n\n");
				break;
			case 7:
				displayStack(pStack);
				break;
			case 8:
				if (!pStack)
					printf("Delete: Failed\n\n");
				else
				{
					deleteArrayStack(pStack);
					pStack = NULL;
					printf("Delete: Success\n\n");
				}
				break;
			case 9:
				loop = 0;
				break;
			default:
				printf("Please Enter a Valid Option\n");
				break;
		}
	}
}

3. arraystack.h

#ifndef _ARRAY_STACK_
#define _ARRAY_STACK_

#include <stdio.h>
#include <stdlib.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 displayStack(ArrayStack *pStack);
int isArrayStackFull(ArrayStack* pStack);
int isArrayStackEmpty(ArrayStack* pStack);
void deleteArrayStack(ArrayStack* pStack);

#endif

#ifndef _COMMON_STACK_DEF_
#define _COMMON_STACK_DEF_

#define TRUE		1
#define FALSE		0

#endif