[자료구조] 스택 - 02 . 배열로 구현하는 스택

[배열로 구현하는 스택]

[배열로 구현하는 스택]

=>동적으로 스택의 용량을 조절하기 어렵다는 단점이 있다 .

=>구현이 간단하다는 장점이 있다.

 

=>배열기반의 스택은 각 노드를 동적으로 생성하고 제거하는 대신, 스택 생성 초기에 사용자가 부여한 용량만큼 노드를

한꺼번에 생성 , 최상위 노드의 위치를 나타내는 변수를 이용하여 삽입과 제거 연산을 수행한다.

 

[스택과 스택의 노드 표현하기]

[노드]

=>스택의 각 층을 구성한다.

=>데이터만 담는 구조체로 표현된다.

(노드의 위치는 배열의 인덱스로 알 수 있어 뒷노드의 포인터는 필요 없다)

typedef int ElementType;

typedef struct tagNode
{
	ElementType Data;
}Node;

[스택 구조체]

=>배열 기반의 스택은 다음 세가지 필드를 가지고 있어야 한다.

• 용량 : 스택이 얼마만큼의 노드를 가질 수 있는지 판단
• 최상의 노드의 위치 : 삽입/제거시에 최상위 노드에 접근하게 도움
• 노드 배열 : 스택에 쌓이는 노드를 보관

typedef strcut tagAttayStack
{
    int Capacity;	//용량
    int Top;		//최상위 노드 위치
    Node* Nodes;	//노드배열
}ArrayStack;

=>노드 배열이 포인터인 것은 포인터를 배열로 사용 사능한 C언어의 특성때문에 그렇다.

(자유 저장소에 할당한 배열의 첫번째 요소를 가리킨다 . )

 

[스택의 기본연산 구현하기]

=>스택은 가장 위에 있는 노드 위에 새로운 노드를 얹는 "삽입"과 "삭제"연산을 수행해야 한다.

 

[스택의 생성]

void AS_CreateStack(ArrayStack** Stack , int Capaity)
{
    //스택을 자유 저장소에 생성
    (*Stack)=(ArrayStack*)malloc(sizeOf(ArrayStack));
    
    //입력된 Capacity만큼의 노드를 자유 저장소에 생성
    (*Stack)->Nodes=(Node*)malloc(sizeof(Node)*Capacity);
    
    //Capacity 및 Top 초기화
    (*Stack)->Capacity=Capacity;
    (*Stack)->Top=0;
}

[스택의 소멸]

void AS_DestroyStack(ArrayStack* Stack)
{
    //노드를 자유 저장소에서 해제
    free(Stack->Nodes);
    
    //스택을 자유 저장소에서 해제
    free(Stack);
}

 

[삽입(Push) 연산]

void AS_Push(ArrayStack* Stack , ElementType Data)
{
	int Position=Stack->Top;
	ArrayStack->Stack[Position].Data=Data;
    Stack->Top++;
}

[제거(Pop) 연산]

=>Top이 가진 값은 실제 최상위 노드보다 1 크기에 -1 하여 생각한다.

ElementArray AS_Pop(ArrayStack* Stack)
{
	int Positioin= -- (Stack->Top);
    return Stack->Node[Position].Data;
}

[배열로 구현하는 스택 예제 프로그램]

[ArrayStack.h]

#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H
#include<stdio.h>
#include<stdlib.h>
//노드
typedef int ElementType;

typedef struct tagNode
{
	ElementType Data;
}Node;

//스택
typedef struct ArrayStack
{
	int Capacity;	//용량
	int Top;		//Top
	Node* Nodes;	//노드
}Stack;

//스택 생성
void AS_CreateStack(ArrayStack** Stack, int Capacity);
//스택 삭제
void AS_DestroyStack(ArrayStack* Stack);
//Push
void AS_Push(ArrayStack* Stack,ElementType Data);
//Pop
ElementType AS_Pop(ArrayStack* Stack);
//Top;
ElementType AS_Top(ArrayStack* Stack);
//GetSzie
int AS_GetSize(ArrayStack* Stack);
//IsEmpty
bool As_IsEmpty(ArrayStack* Stack);
//IsFull
bool As_IsFull(ArrayStack* Stack);
#endif // !ARRAYSTACK_H

[ArrayStack.c]

#include "ArrayStack.h"

//스택 생성
void AS_CreateStack(ArrayStack** Stack, int Capacity)
{
	(*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack));
	(*Stack)->Nodes = (Node*)malloc(sizeof(Node) * Capacity);
	(*Stack)->Capacity = Capacity;
	(*Stack)->Top = 0;
}
//스택 삭제
void AS_DestroyStack(ArrayStack* Stack)
{
	free(Stack->Nodes);
	free(Stack);
}
//Push
void AS_Push(ArrayStack* Stack, ElementType Data)
{
	int position = Stack->Top;
	Stack->Nodes[position].Data = Data;
	Stack->Top++;
}
//Pop
ElementType AS_Pop(ArrayStack* Stack)
{
	int position = --(Stack->Top);
	return Stack->Nodes[position].Data;
}
//Top
ElementType AS_Top(ArrayStack* Stack)
{
	int position = (Stack->Top) - 1;
	if (position < 0)
		position = 0;
	return Stack->Nodes[position].Data;
}
//GetSzie
int AS_GetSize(ArrayStack* Stack)
{
	return (Stack->Top);
}
//IsEmpty
bool As_IsEmpty(ArrayStack* Stack)
{
	return (Stack->Top == 0);
}
//IsFull
bool As_IsFull(ArrayStack* Stack)
{
	return (Stack->Top == Stack->Capacity);
}

[ArrayStackTest.c]

#include "ArrayStack.h"

int main(void)
{
	int i = 0;
	ArrayStack* Stack = NULL;

	AS_CreateStack(&Stack, 10);

	AS_Push(Stack, 3);
	AS_Push(Stack, 37);
	AS_Push(Stack, 11);
	AS_Push(Stack, 12);

	printf("Capacity : %d , Size : %d , Top : %d\n\n", Stack->Capacity, AS_GetSize(Stack), AS_Top(Stack));

	for (int i = 0; i < 4; i++)
	{
		if (As_IsEmpty(Stack))
			break;

		printf("Popped : %d\t", AS_Pop(Stack));

		if (!As_IsEmpty(Stack))
			printf("Current Top: %d\n", AS_Top(Stack));
		else
			printf("Stack Is Empty.\n");
	}

	AS_DestroyStack(Stack);
	return 0;
}