스택-자료구조<6>

hans·2022년 4월 24일

자료구조 공부 정리

목록 보기

6/14

오늘은 자료구조 스택에 대해 공부해본 것을 정리해 보도록 하자
먼저 스택의 특징에 대해 간략하게 알아보자

스택의 특징

스택이란 흔히 LEFO 구조의 자료구조 이다
LEFO란 (Last-In,First-Out)의 약자로 후입선출 이라고도 불린다
LEFO의 예시를 들기위해 상자 쌓기를 살펴보자

우리에게 1번 상자가 있다고 생각해 보자 다음번 2번상자는 어떻게 쌓을 것인가?

당연하게도 1번상자 위에 우리는 2번상자를 올릴거다 그렇다면 우리가 4번상자까지 쌓은모습을 상상해 보자

그럼 이번에는 2번 상자를 열어보도록 하자
바로 2번을뺀다면 상자더미는 무너질거다 그렇기에 우리는 맨위에서 부터 상자를 빼내보자

이제 상자를 뺴면 우리는 2번 상자를 열수있는 상태가 되었다

이것이 스택의 간략한 구조이다
그렇다면 이제부터 본격적으로 스택을 구현해 보자

스택의 ADT

스택을 구현하기 위해 먼저 스택의 ADT를 정의해보자

스택의 ADT

1.void StackInit(Stack * pstack);
--스택의 초기화를 진행
--스택 생성 후 가장먼저 호출

2.int SIsEmpty(Stack * pstack);
--스택이 빈 경우(1),않은 경우(0)을 반환한다

3.void SPush(Stack * pstack, Data data);
--스택에 데이터를 저장한다 (상자를 쌓는다)
--매개변수 data로 전달된 값을 저장한다

4.int SPop(Stack * pstack);
--마지막에 저장된 요소를 삭제한다 (맨위 상자를 빼낸다)
--삭제된 데이터는 반환한다 (데이터 == 상자의 내용물)
--함수를 호출하기 위해서는 데이터가 하나 이상 존재해야 함을 보장해야한다

5.int SPeek(Stack * pstack);
--마지막에 저장된 요소를 반환하되 삭제하지 않는다 (맨위 상자의 내용물을 보기만 하고 뺴지는 않는다)
--함수를 호출하기 위해서는 데이터가 하나 이상 존재해야 함을 보장해야 한다

배열 기반 스택

우리는 배열 기반 스택에 대해 알아보자
우리가 5개의 데이터를 담는 배열을 선언했다고 생각해보자

topIndex는 제일 위에 있는 데이터가 몇번째에 위치해 있는지를 나타내는 표시이다
여기에 데이터를 "A"을 추가해 보자

배열의 0번째에 데이터가 추가되었고 topIndex는 0이 되었다
이방식을 통해 배열 기반 스택을 구현해 보자

스택의 코드

typedef struct _arrayStack
{
	int stackArr[100];
	int topIndex;
} ArrayStack;

배열의 크기는 int를 담을공간 100개
topIndex를 선언한다

void StackInit(Stack * pstack)
{
	pstack->topIndex = -1;
}

스택 초기화를 통해서 topIndex에 -1을 넣는다

int SIsEmpty(Stack * pstack)
{
	if(pstack->topIndex == -1)
		return 1;
	else
		return 0;
}

topIndx를 통해서 스택안에 데이터의 유무를 파악한다

void SPush(Stack * pstack, Data data)
{
	pstack->topIndex += 1;
	pstack->stackArr[pstack->topIndex] = data;
}

int SPop(Stack * pstack)
{
	int rIdx;

	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	rIdx = pstack->topIndex;
	pstack->topIndex -= 1;

	return pstack->stackArr[rIdx];
}

int SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->stackArr[pstack->topIndex];
}

연결 리스트 기반 스택

앞서 많이 소개한 리스트의 구조이다 이것을 통해 스택을 구현해 보자

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

구조체 노드 정의

typedef struct _listStack
{
	Node * head;
} Stack;

연결 리스트 기반 스택의 구현은 head 를 사용한다

void StackInit(Stack * pstack)
{
	pstack->head = NULL;
}

int SIsEmpty(Stack * pstack)
{
	if(pstack->head == NULL)
		return 1;
	else
		return 0;
}

스택의 데이터 존재 유무를 파악한다


void SPush(Stack * pstack, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));

	newNode->data = data;
	newNode->next = pstack->head;

	pstack->head = newNode;
}

int SPop(Stack * pstack)
{
	int rdata;
	Node * rnode;

	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	rdata = pstack->head->data;
	rnode = pstack->head;

	pstack->head = pstack->head->next;
	free(rnode);

	return rdata;
}