C로 만드는 자료구조-배열로 구현한 스택

배열 스택(Array Stack)란?

  배열을 이용해 구현한 스택을 의미한다. 배열 리스트와 마찬가지로 물리적으로 연결되어있어야 하며 그에 따라 스택을 생성할 때 무조건 스택의 크기를 미리 지정해 주어야 한다.

각 함수 중간에 AS가 있는데 ArrayStack을 의미한다.

배열 스택의 구현

소스 파일 구성은 다음과 같다.

파일 이름	내용
arraystack.h	구조체 및 함수 선언
arraystack.cpp	함수 구현
arraystackmain.cpp	main 함수 실행

1.arraylist.h

#pragma once
#include<iostream>
using namespace std;
#define TRUE 1
#define FALSE 0

typedef struct ArrayStackNode {
	int data;
};

typedef struct ArrayStack {
	int maxSize;
	int currentSize;
	ArrayStackNode *pElement;
};

ArrayStack* createAS(int max);//스택 생성
int pushAS(ArrayStack* pStack, ArrayStackNode element);// 스택 push
ArrayStackNode* popAS(ArrayStack* pStack);//스택 pop
ArrayStackNode* peekAS(ArrayStack* pStack);//스택 peek
int isASFull(ArrayStack* pStack);// 스택의 자료가 꽉는 지 여부
int isASEmpty(ArrayStack* pStack);// 빈 스택인지 확인
void deleteAS(ArrayStack* pStack);// 스택 삭제
void displayAS(ArrayStack *pStack);//스택 자료들을 출력한다

- ArrayStackNode는 스택에 저장되는 각각의 자료들을 의미하면 실제 값인 data를 포함한다. 이렇게 따로 노드 구조체를 만드는 이유는 범용성을 위해서 이다.  
- ArrayStack는 실제 스택을 의미하며 스택의 최대 자료 저장 개수(maxSize), 현재 저장된 자료 개수(currentSize), 실제로 자료를 저장 중인 배열(pElement)을 포함한다.

전체적인 형태는 다음과 같다.

추가적으로 #define을 이용해 TURE은 1,FALSE는 0 값으로 정의해주었다.
함수들은 함수 구현 부분에서 자세히 설명하겠다.

2.arraystack.cpp

- createAS()

ArrayStack* createAS(int max) {
	ArrayStack* pReturn = NULL;

	if (max > 0) {
		pReturn = new ArrayStack;
		if (pReturn != NULL) {
			memset(pReturn, 0, sizeof(ArrayStack));
			pReturn->maxSize = max;
		}
		else {
			cout << "메모리 할당 오류" << endl;
		}
	}
	pReturn->pElement = new ArrayStackNode;
	if (pReturn->pElement != NULL) {
		memset(pReturn->pElement, 0, sizeof(ArrayStackNode)*max);
	}
	else {
		cout << "메모리 할당 오류" << endl;
		delete pReturn;
	}
	return pReturn;
}

 먼저 최대 저장 가능 원소 개수가 0보다 큰지 확인 후 0보다 크다면 ArrayStack에 대한 메모리를 할당 후 maxSize를 max값으로 초기화하고 pElement에 대해서도 메모리 할당 후 memset()을 이용해서 max만큼 메모리를 할당한다.

- push()

 먼저 push 연산을 하기 위해서는 스택이 가득 차 있는 상태인지 아닌지를 알아야 한다. 이때 isASFull() 함수를 이용해 스택이 가득 차있는 상태인지 아닌지를 알아내 push 연산이 가능한지 판단할 것이다. 스택이 가득 찬 상태가 아니라면 pElement에서 가장 끝 부분에 새로운 노드 element를 추가한다. 이때 반환형은 TRUE/FALSE이다.

pStack->pElement [pStack->current] = element; // 스택의 끝에 노드 추가
pStack->currentSize++;// 탑 위치 변경

그림으로 나타내면 다음과 같다.

코드 구현은 다음과 같다.

int pushAS(ArrayStack* pStack, ArrayStackNode element) {
	int ret = FALSE;
	if (pStack != NULL) {
		if (isASFull(pStack)==FALSE) {
			pStack->pElement[pStack->currentSize] = element;
			pStack->currentSize++;
			ret = TRUE;
		}
		else {
			cout << "오류,가득 찬 스택이 입니다. overflow" << endl;
		}
	}
	return ret;
}// 스택 push

 

- pop()

 먼저 pop 연산을 하기 위해서는 스택이 공백 상태인지 아닌지를 알아야 한다. 이때 isASEmpty() 함수를 이용해 스택이 공백 상태인지 아닌지를 알아내 pop 연산이 가능한지 판단할 것이다. 스택이 공백 상태가 아니라면 pElement에서 가장 끝 부분에 존재하는 노드를 반환한다. 이때 노드를 반환할 때는 새로운 노드를 생성 후 탑에 있는 노드의 포인터를 전달한다.
반환 후 에는 탑에 있는 노드를 제거해야 하는데 직접 메모리를 초기화 하기보다는 현재 탑의 위치를 변경하는 방식을 이용한다. 실제 탑의 위치를 변경했기 때문에 만약 이후에 새로운 노드가 추가되더라도 덮어쓰기(overwrite)가 되기 때문에 문제가 없다. 추가적으로 이때 반환되는 값은 새롭게 메모리를 할당하기 때문에 메모리를 해제하는 과정이 필요하다. 이 과정은 main함수에서 실행할 예정이다.

pReturn = new ArrayStackNode;// 새로운 메모리 할당
*pReturn = pStack->pElement [pStack->currentSize - 1]; // 탑에 위치한 노드를 대입
pStack->currentSize--;// 탑 위치 변경

그림으로 나타내면 다음과 같다.

코드 구현은 다음과 같다.

ArrayStackNode* popAS(ArrayStack* pStack) {
	ArrayStackNode* pReturn=NULL;
	if (pStack != NULL) {
		if (isASEmpty(pStack)==FALSE) {
			pReturn = new ArrayStackNode;
			if (pReturn != NULL) {
				*pReturn = pStack->pElement[pStack->currentSize - 1];
				pStack->currentSize--;
			}
		}
		else {
			cout << "오류,빈 스택입니다. underflow" << endl;
		}
	}
	return pReturn;
}//스택 pop

 

- peek()

 peek 연산은 pop연산과 완전히 똑같다. 단지 탑의 위치를 변경하지만 않으면 된다. 또한 반환되는 노드가 제거되지 않기 때문에 반환되는 노드에 대해 메모리 해제를 해주지 않아도 된다.

그림으로 나타내면 다음과 같다.

코드 구현은 다음과 같다.

ArrayStackNode* peekAS(ArrayStack* pStack) {
	ArrayStackNode* pReturn=NULL;
	if (pStack != NULL) {
		if (isASEmpty(pStack) == FALSE) {
			pReturn = new ArrayStackNode;
			if (pReturn != NULL) {
				*pReturn = pStack->pElement[pStack->current - 1];
			}
		}
		else {
			cout << "오류,빈 스택입니다. underflow" << endl;
		}
	}
	return pReturn;
}//스택 peek

 

나머지 함수 구현 코드는 다음과 같다.

int isASFull(ArrayStack* pStack) {
	int ret = FALSE;
	if (pStack != NULL) {
		if (pStack->currentSize == pStack->maxSize) {
			ret = TRUE;
		}
	}
	return ret;
} //스택의 자료가 꽉는 지 여부
int isASEmpty(ArrayStack* pStack) {
	int ret = FALSE;
	if (pStack != NULL) {
		if (pStack->currentSize == 0) {
			ret = TRUE;
		}
	}
	return ret;
}// 빈 스택인지 확인
void deleteAS(ArrayStack* pStack) {
	if (pStack != NULL) {
		if (pStack->pElement != NULL) {
			delete[] pStack->pElement;
		}
		delete pStack;
	}
}// 스택 삭제
void displayAS(ArrayStack *pStack) {
	if (pStack != NULL) {
		int top = pStack->currentSize;
		cout << "스택 크기: " << pStack->maxSize << "\t";
		cout << "현재 자료 개수: " << pStack->current << endl;
		
		cout << "스택 자료 출력  " << "(맨 왼쪽이 top)" << endl;
		for (int i = top - 1; i >= 0; i--) {
			cout << pStack->pElement[i].data << "\t";
		}
		cout << endl;
	}
}

 

3.arraystackMain.cpp

메인 함수 실행 코드는 다음과 같다.

#include "stdafx.h"
#include "arraystack.h"
int main() {
	ArrayStack *pStack = NULL;
	ArrayStackNode *pNode = NULL;

	pStack = createAS(6);
	if (pStack != NULL) {
		ArrayStackNode node1 = { 1 };
		ArrayStackNode node2 = { 3 };
		ArrayStackNode node3 = { 5 };
		ArrayStackNode node4 = { 7 };

		
		pushAS(pStack, node1);
		pushAS(pStack, node2);
		pushAS(pStack, node3);
		pushAS(pStack, node4);
		displayAS(pStack);

		cout << endl;

		pNode = popAS(pStack);
		if (pNode != NULL) {
			cout <<"pop:" <<pNode->data << endl;
			delete pNode;
		}
		else {
			cout << "빈 스택입니다." << endl;
		}
		
		cout << endl;
		displayAS(pStack);

		cout << endl;
		pNode = peekAS(pStack);
		if (pNode != NULL) {
			cout <<"peek: " <<pNode->data << endl;
		}
		else {
			cout << "빈 스택입니다." << endl;
		}
		
		cout << endl;
		displayAS(pStack);
	}
	return 0;
}

 여기서 주의해야 할 점은 pop 연산 후 반환되는 노드(pNode)에 대해 메모리 해제를 해줘야 한다는 점이다. 위 코드에서는 delete pNode;를 통해 메모리 해제를 해주었다.

실행결과는 다음과 같다.