[자료구조] ch 2. 스택 (1)

2.1 스택 ADT

 

2.1.1 스택의 개념

 

- 스택에서 데이터 입/출력은 오로지 스택의 꼭대기에서만 이루어짐

- 가장 마지막에 들어간 데이터가 제일 먼저 나오고(LIFO Last-In-First Out) 가장 먼저 들어간 데이터는 가장 나중에 나옴(FILO First In Last out)

 

2.1.2 스택의 핵심 기능 : 삽입과 제거 연산

 

삽입 연산 

- 스택 위에 새로운 노드(요소)를 "쌓는" 일

 

제거 연산

- 스택에서 최상위 노드를 "걷어"냄

 

 

2.2 배열로 구현하는 스택

 

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

- 최상위 노드의 위치를 나타내는 변수를 두고 삽입과 제거 연산 수행 

 

2.2.1 배열 기반 스택과 스택의 노드 표현 

 

노드 구조체 

 

 - 데이터만 담는 구조체로 표현 

 - 노드가 존재하는 위치는 배열의 인덱스로 알 수 있기 때문에 이전이나 다음 노드에 대한 포인터 필요 없음

typedef int ElementType;

typedef struct tagNode 
{
   ElementType Data;
} Node;

 

스택 구조체 

 

- 용량 : 스택이 얼마만큼의 노드를 가질 수 있는지 알기 위해 사용

- 최상위 노드의 위치 : 삽입/제거 연산을 할 때 최상위 노드에 접근할 수 있게 도와줌

- 노드 배열 : 스택에 쌓이는 노드를 보관하는 데 사용 

- 노드 배열을 힙에 할당하고 Nodes 포인터는 힙에 할당한 배열을 가리키는 용도로 사용 

- Nodes 포인터는 힙에 할당한 배열의 첫 번째 요소를 가리킴

 

typedef struct tagArrayStack
{
    int Capacity;
    int Top;
    Node* Nodes;
}ArrayStack;

 

2.2.2 배열 기반 스택의 기본 연산 

 

스택 및 노드 생성 함수 AS_CreateStack()

 

- 스택을 생성하고 노드를 받아들일 공간을 준비

- Top는 노드가 삽입될 때마다 1씩 증가하고 노드가 삭제될 때마다 1씩 감소  

void AS_CreateStack(ArrayStack**, int Capacity)
{
	//스택을 힙에 생성
    (*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack));
    
    //입력된 Capacity만큼의 노드를 힙에 생성
    (*Stack) = (Node*)malloc(sizeof(Node)*Capacity);
    
    //Capacity 및 Top 초기화 
    (*Stack)->Capacity = Capacity;
    (*Stack)->Top = -1;
}

 

스택 및 노드 삭제 함수 AS_DesrotyStack()

 

- 스택 내의 노드와 스택을 삭제 

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

 

노드 삽입 함수 AS_Push

 - 최상위 노드의 인덱스(Top)에서 1을 더한 곳에 새 노드를 입력하도록 구현

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

 

노드 제거 함수 AS_Pop 

 - 최상위 노드의 인덱스(Top)값을 1만큼 낮추도록 구현

 - 제거 연산에서는 최상위 노드에 있던 데이터를 호출자에게 반환해야 함

ElementType AS_Pop(ArrayStack* Stack)
{
    int Position = Stack->Top--;
    return Stack->Nodes[Postion].Data;
}

 

2.2.3 배열 기반 스택 예제 프로그램

 

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct tagNode
{
	ElementType Data;
}Node;

typedef struct tagArrayStack
{
	int Capacity;
	int Top;
	Node* Nodes;
}ArrayStack;


//스택 및 노드 생성
void AS_CreateStack(ArrayStack** Stack, int Capacity)
{
	//스택을 힙에 생성
	(*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack));

	//입력된 Capacity만큼의 노드를 힙에 생성
	(*Stack)->Nodes = (Node*)malloc(sizeof(Node) * Capacity);

	//Capacity 및 Top 초기화 
	(*Stack)->Capacity = Capacity;
	(*Stack)->Top = -1;
}

//스택 및 노드 해제 
void AS_DestroyStack(ArrayStack* Stack)
{
	//노드를 힙에서 해제 
	free(Stack->Nodes);

	//스택을 힙에서 해제 
	free(Stack);
}

//노드 삽입
void AS_Push(ArrayStack* Stack, ElementType Data)
{
	Stack->Top++;
	Stack->Nodes[Stack->Top].Data = Data;
}

//노드 제거 
ElementType AS_Pop(ArrayStack* Stack)
{
	int Position = Stack->Top--;
	return Stack->Nodes[Position].Data;
}

//최상위 노드 반환
ElementType AS_Top(ArrayStack* Stack)
{
	return Stack->Nodes[Stack->Top].Data;
}

//스택 크기 반환
int AS_GetSize(ArrayStack* Stack)
{
	return Stack->Top + 1;
}

//스택이 비어있는지 검사 
int AS_IsEmpty(ArrayStack* Stack)
{
	return (Stack->Top == -1);
}

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 (i = 0; i < 4; i++)
	{
		if (AS_IsEmpty(Stack))
			break;
		printf("Popped:%d", 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;

}

 

 

2.3 링크드 리스트로 구현하는 스택 

 

2.3.1 링크드 리스트 기반 스택과 스택의 노드 표현

 

- 링크드 리스트로 스택을 구현하려면 노드는 자신의 위에 위치하는 노드에 대한 포인터를 갖고 있어야 함 

- 노드 구조체 

typedef struct tagNode
{
    char* Data;
    struct tagNode* NextNode;
}Node;

1) char* Data;

 - 힙에 할당된 문자열의 주소를 가리킴

 - char* 형은 포인터이기 때문에 문자열이 저장된 주소만 담을 수 있음

 

2) struct tagNode* NextNode;

 - 자기위에 쌓여있는 노드의 주소를 가리킴

 

 

- 링크드 리스트 스택의 구조체 

typedef struct tagLinkedListStack
{
    Node* List;
    Node* Top;
}LinkedListStack;

1) Node* List;

 - 데이터를 담는 링크드 리스트를 가리킴

 - 힙에 존재하는 헤드 노드의 주소를 가리킴

 

2)Node* Top;

 - 힙에 존재하는 테일 노드의 주소를 가리킴

 - 스택의 입출력이 이루어지는 최상위 노드에 대한 포인터 

 

2.3.2 링크드 리스트 기반 스택의 기본 연산

 

스택 생성 함수 LLS_CreateStack

 - LinkedListStack 구조체를 힙에 할당

void LLS_CreateStack(LinkedListStack** Stack)
{
    //스택을 힙에 생성
    (*Stack) = (LinkedListStack*)malloc(LinkedListStack));
    (*Stack)->List = NULL;
    (*Stack)->Top = NULL;
}

 

스택 소멸 함수 LLS_DestroyStack

 - 먼저 각 노드를 제거하고 힙에서 LinkedListStack 구조체를 할당 해제 

void LLS_DestroyStack(LinkedListStack* Stack)
{
    while(!LLS_IsEmpty(Stack))
    {
    	Node*Propped = LLS_Pop(Stack);
        LLS_DestroyNode(Popped);
    }
    
    //스택을 힙에서 해제 
    free(Stack);
}

 

노드 생성 함수 LLS_CreateNode

 - 노드를 힙에 생성할 떄 문자열을 저장할 공간도 함께 생성해야 함 

Node* LLS_CreateNode(char* NewData)
{
    Node* NewNode = (Node*)malloc(sizeof(Node)); //Node 구조체 할당 
    NewNode->Data = (char*)malloc(strlen(NewData)+1); // Node 구조체의 Data 필드 할당
    
    strcpy(NewNode->Data, NewData); //데이터를 저장
    
    NewNode->NextNode = NULL; //다음 노드에 대한 포인터는 NULL로 초기화 
    
    return NewNode; // 노드의 주소를 반환
}

 

노드 소멸 함수 LLS_DestroyNode

 - 노드를 메모리에서 제거 

void LLS_DestroyNode(Node*_Node)
{
   free(_Node->Data); //노드의 힙에서 Data 필드 할당 해제 
   free(_Node); //노드 할당 해제 
}

 

노드 삽입 함수 LLS_Push

 - 삽입 연산은 스택의 최상위 노드 Top에 새 노드를 얹도록 구현 

 - 새 노드가 최상위 노드가 됨

 - 새로운 최상위 노드의 주소를 LinkedListStack 구조체의 Top 필드에 등록

void LLS_Push(LinkedListStack* Stack, Node* NewNode)
{
    if(Stack->List == NULL)
    {
    	Stack->List = NewNode;
    }
    else
    {
    	//스택의 Top 위에 새 노드를 얹음
        Stack->Top->NextNode = NewNode;
    }
    
    //스택의 Top 필드에 새 노드의 주소를 등록
    Stack->Top = NewNode;
}

 

노드 제거 함수 LLS_Pop

 - 현재 최상위 노드(Top)의 주소를 다른 포인터에 복사 

 - 새로운 최상위 노드 (현재 최상위 노드)의 바로 아래(이전)노드를 찾음

 - LinkedListStack 구조체의 Top 필드에 새로운 최상위 노드의 주소를 등록

 - 아까 저장했던 예전 최상위 노드의 주소를 반환 

Node* LLS_Pop(LinkedListStack * Stack)
{
    //LLS_Pop() 함수가 반환할 최상위 노드 저장
    Node* TopNode = Stack->Top;
    
    if(Stack->List == Stack->Top)
    {
    	Stack->List = NULL;
        Stack->Top = NULL:
    }
    else
    {
    	//Top 아래에 있던 노드를 새로운 CurrentTop에 저장
        Node* CurrentTop = Stack->List;
        while( CurrentTop != NULL && CurrentTop->NextNode != Stack->Top)
        {
        	CurrentTop = CurrentTop->NextNode;
        }
        
        //CurrentTop을 Top에 저장
        Stack->Top = CurrentTop;
        Stack->Top->NextNode = NULL;
    }
    
    return TopNode;
}

 

2.3.3 링크드 리스트 기반 스택 예제 프로그램

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//노드 구조체
typedef struct tagNode
{
	char* Data; //힙에 할당된 문자열의 주소를 가리킴
	struct tagNode* NextNode; //자기 위에 쌓여있는 노드의 주소를 가리킴
}Node;

//스택 구조체 
typedef struct tagLinkedListStack
{
	Node* List; //힙에 존재하는 헤드 노드의 주소를 가리킴
	Node* Top; //힙에 존재하는 테일 노드의 주소를 가리킴
}LinkedListStack;

void LLS_CreateStack(LinkedListStack** Stack);
void LLS_DestroyStack(LinkedListStack* Stack);

Node* LLS_CreateNode(char* Data);
void LLS_DestroyNode(Node* _Node);

void LLS_Push(LinkedListStack* Stack, Node* NewNode);
Node* LLS_Pop(LinkedListStack* Stack);

Node* LLS_Top(LinkedListStack* Stack);
int LLS_GetSize(LinkedListStack* Stack);
int LLS_IsEmpty(LinkedListStack* Stack);

int main(void)
{
	int i = 0;
	int Count = 0;
	Node* Popped;

	LinkedListStack* Stack;

	LLS_CreateStack(&Stack);

	LLS_Push(Stack, LLS_CreateNode("abc"));
	LLS_Push(Stack, LLS_CreateNode("def"));
	LLS_Push(Stack, LLS_CreateNode("efg"));
	LLS_Push(Stack, LLS_CreateNode("hij"));

	Count = LLS_GetSize(Stack);
	printf("Size:%d, Top:%s\n\n", Count, LLS_Top(Stack)->Data);

	for (i = 0; i < Count; i++)
	{
		if (LLS_IsEmpty(Stack))
			break;
		Popped = LLS_Pop(Stack);

		printf("Popped:%s", Popped->Data);

		LLS_DestroyNode(Popped);

		if (!LLS_IsEmpty(Stack))
		{
			printf("Current Top: %s\n", LLS_Top(Stack)->Data);
		}
		else
		{
			printf("Stack Is Empty\n");
		}
	}

	LLS_DestroyStack(Stack);

	return 0;
}

	//스택 생성 
	void LLS_CreateStack(LinkedListStack * *Stack)
	{
		//스택을 힙에 생성
		(*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack));
		(*Stack)->List = NULL;
		(*Stack)->Top = NULL;
	}

	//스택 소멸 
	void LLS_DestroyStack(LinkedListStack * Stack)
	{
		//각 노드 제거 
		while (!LLS_IsEmtpy(Stack))
		{
			Node* Propped = LLS_Pop(Stack);
			LLS_DestroyStack(Propped);
		}

		//스택을 힙에서 해제 
		free(Stack);
	}

	//노드 생성
	Node* LLS_CreateNode(char* NewData)
	{
		//Node 구조체 메모리 할당
		Node* NewNode = (Node*)malloc(sizeof(Node));
		//Node 구조체의 Data 필드 메모리 할당
		NewNode->Data = (char*)malloc(strlen(NewData) + 1);

		strcpy_s(NewNode->Data,100, NewData); //데이터 저장

		NewNode->NextNode = NULL; //다음 노드에 대한 포인터는 NULL로 초기화 

		return NewNode; //노드의 주소를 반환
	}

	//노드 소멸
	void LLS_DestroyNode(Node * _Node)
	{
		free(_Node->Data);
		free(_Node);
	}

	//노드 삽입
	void LLS_Push(LinkedListStack * Stack, Node * NewNode)
	{
		if (Stack->List == NULL)
		{
			Stack->List = NewNode;
		}
		else
		{
			//스택의 Top에 신규 노드를 연결
			Stack->Top->NextNode = NewNode;
		}

		//스택의 Top 필드에 새 노드의 주소를 등록
		Stack->Top = NewNode;
	}

	//노드 제거 
	Node* LLS_Pop(LinkedListStack * Stack)
	{
		//LLS_Pop() 함수가 반환할 최상위 노드 저장
		Node* TopNode = Stack->Top;

		if (Stack->List == Stack->Top)
		{
			Stack->List = NULL;
			Stack->Top = NULL;
		}
		else
		{
			//Top 아래에 있던 노드를 새로운 CurrentTop에 저장
			Node* CurrentTop = Stack->List;
			while (CurrentTop != NULL && CurrentTop->NextNode != Stack->Top)
			{
				CurrentTop = CurrentTop->NextNode;
			}

			//CurrentTop을 Top에 저장 
			Stack->Top = CurrentTop;
			Stack->Top->NextNode = NULL;
		}

		return TopNode;
	}

	//최상위 노드 반환 
	Node* LLS_Top(LinkedListStack * Stack)
	{
		return Stack->Top;
	}

	//스택 사이즈 
	int LLS_GetSize(LinkedListStack * Stack)
	{
		int Count = 0;
		Node* Current = Stack->List;

		while (Current != NULL)
		{
			Current = Current->NextNode;
			Count++;
		}

		return Count;
	}

	//스택이 비어있는지 확인
	int LLS_IsEmpty(LinkedListStack * Stack)
	{
		return (Stack->List == NULL);
	}