자료구조 만들기 #1 스택

구조체, 리스트를 사용한 자료구조 만들어보기 첫번째

스택

다 만드는데 대충 2시간쯤 걸렷나? 싶다 간만에 하니까 기억이 가물가물하네

기본적으로 스택은 리스트의 한 유형에 해당한다. 

LIFO(Last In Frist Out/후입 선출)이라는 구조를 가지고 있는데, 

가장 마지막에 입력된 자료가 맨 처음 수행되는 하노이의 탑쌓기라고 생각하면 된다. 

스택이 중요한건 컴퓨터가 메모리 상에서도 스택이라는 구조를 사용하기도 하지만, 운영체제 입장에서도 다른것은 신경쓸 필요 없이 최상위 데이터만 신경쓰면 되기에 처리 속도면에서 효율적인 자료구조라고 볼 수 있다.

스택이 비었을 경우의 동작

 

스택에 자료를 입력한 이후의 동작

/**
* 스택자료구조 구현하기
* //리스트
* using struct
* 
*/
#define _CRT_SECURE_NO_WARNINGS

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

typedef struct Node{
	struct Node* next;
	char* data;
} Node;

//초기 공백노드 설정
int stackSize = 0;
Node* top = NULL;

void menu(int n);
int isEmpty();
int push();
int pop();
void search();
void printStack();
void freeStack();

int main() {

	while (1)
	{
		int input;
		printf("1 : stack push , 2 : stack pop, 3 : search data, 4 : print stack, 0 : 프로그램 종료\n");
		scanf("%d", &input);
		menu(input);
	}
	return 0;
}

// 명령어 입력기
void menu(int n) {
	if (n == 0)
	{
		freeStack();
		printf("프로그램을 종료합니다.\n");
		exit(0);
	}
	else if (n == 1)
	{
		push();
	}
	else if (n == 2)
	{
		pop();
	}
	else if (n == 3)
	{
		search();
	}
	else if (n == 4)
	{
		printStack();
	}
	else
	{
		printf("잘못된 입력입니다. 다시 입력해주세요.\n");
	}
}

int isEmpty()
{
	//스택이 비었다면 true
	if (stackSize == 0)
	{
		printf("스택이 비어있습니다.\n");
		return 1;
	}
	else
	{
		return 0;
	}
}

int push()
{
	printf("저장할 단어를 입력해주세요. 단어의 길이는 최대 255입니다.\n");
	char inputData[256] ;
	scanf("%255s", inputData);
	getchar();

	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL) {
		printf("push실패!! 다시 시도해주세요.\n");
		return -1;
	}
	newNode->data = _strdup(inputData);
	newNode->next = top;
	top = newNode;
	++stackSize;
	return 0;
}

int pop()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return;
	}
	Node* temp = top;
	top = top->next;
	printf("제거된 단어 : %s\n", temp->data);
	free(temp->data);
	free(temp);
	stackSize--;
	return 0;
}

void search()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return;
	}
	printf("찾고  싶은 단어를 입력하세요.\n");
	char inputData[256];
	scanf("%255s", inputData);
	getchar();

	Node* temp = top;
	int isFounded = 0;
	for (int i = stackSize; i > 0; --i) 
	{
		if (strcmp(inputData, temp->data) == 0)
		{
			isFounded = 1;
			printf("%s의 위치는 %d입니다.\n", inputData, i);
			break;
		}
		temp = temp->next;
	}
	if (!isFounded)
	{
		printf("%s은/는 스택에 없습니다.\n", inputData);
	}
}

void printStack()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return;
	}
	Node* temp = top;
	for (int i = stackSize; i > 0; --i)
	{
		printf("스택의 위치 : %d, 저장된 단어 : %s\n", i, temp->data);
		temp = temp->next;
	}
}

void freeStack() {
	while (top != NULL) {
		Node* temp = top;
		top = top->next;
		free(temp->data); // 문자열 메모리 해제
		free(temp); // 노드 메모리 해제
	}
}

 

 

++

사소한 수정점을 찾아냈다.

프로그램을 종료할 때 직접 free()함수를 호출하는것이 아니라 pop함수를 스택이 빌 때 까지 호출하는것이 옳다.

최종 수정 

최종코드

/**
* 스택자료구조 구현하기
* //리스트
* using struct
* 
*/
#define _CRT_SECURE_NO_WARNINGS

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

typedef struct Node{
	struct Node* next;
	char* data;
} Node;

//초기 공백노드 설정
int stackSize = 0;
Node* top = NULL;

void menu(int n);
int isEmpty();
int push();
void pop();
void search();
void printStack();
void freeStack();

int main() {

	while (1)
	{
		int input;
		printf("1 : stack push , 2 : stack pop, 3 : search data, 4 : print stack, 0 : 프로그램 종료\n");
		scanf("%d", &input);
		menu(input);
	}
	return 0;
}

// 명령어 입력기
void menu(int n) {
	if (n == 0)
	{
		freeStack();
		printf("프로그램을 종료합니다.\n");
		exit(0);
	}
	else if (n == 1)
	{
		push();
	}
	else if (n == 2)
	{
		pop();
	}
	else if (n == 3)
	{
		search();
	}
	else if (n == 4)
	{
		printStack();
	}
	else
	{
		printf("잘못된 입력입니다. 다시 입력해주세요.\n");
	}
}

int isEmpty()
{
	//스택이 비었다면 true
	if (stackSize == 0)
	{
		printf("스택이 비어있습니다.\n");
		return 1;
	}
	else
	{
		return 0;
	}
}

int push()
{
	printf("저장할 단어를 입력해주세요. 단어의 길이는 최대 255입니다.\n");
	char inputData[256] ;
	scanf("%255s", inputData);
	getchar();

	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL) {
		printf("push실패!! 다시 시도해주세요.\n");
		return -1;
	}
	newNode->data = _strdup(inputData);
	newNode->next = top;
	top = newNode;
	++stackSize;
	return 0;
}

void pop()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return;
	}
	Node* temp = top;
	top = top->next;
	printf("제거된 단어 : %s\n", temp->data);
	free(temp->data);
	free(temp);
	stackSize--;
}

void search()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return;
	}
	printf("찾고  싶은 단어를 입력하세요.\n");
	char inputData[256];
	scanf("%255s", inputData);
	getchar();

	Node* temp = top;
	int isFounded = 0;
	for (int i = stackSize; i > 0; --i) 
	{
		if (strcmp(inputData, temp->data) == 0)
		{
			isFounded = 1;
			printf("%s의 위치는 %d입니다.\n", inputData, i);
			break;
		}
		temp = temp->next;
	}
	if (!isFounded)
	{
		printf("%s은/는 스택에 없습니다.\n", inputData);
	}
}

void printStack()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return;
	}
	Node* temp = top;
	for (int i = stackSize; i > 0; --i)
	{
		printf("스택의 위치 : %d, 저장된 단어 : %s\n", i, temp->data);
		temp = temp->next;
	}
}

void freeStack() {
	while (top != NULL) {
		pop();
	}
}

+++

printStack함수는 일부러 위부터 출력시켰습니다. 그게 스택이니까!

 

 

 

 

+++++

까먹고 C++코드를 안올렷네요.

/**
*
* 스택자료구조 구현하기
* //리스트
* 
* using class
*/

#include <iostream>
#include <string>

using namespace std;

class Node {
public:
	string data;
	Node* next;
	
	Node(string data) : data(data), next(nullptr) {}
};

class Stack {
private:
	Node* top;
	int stackSize;

public:
	// 생성자
	Stack() : top(nullptr), stackSize(0){}

	// 소멸자
	~Stack() {
		freeStack();
	}
	bool isEmpty();
	int push();
	void pop();
	void search();
	void printStack();
	void freeStack();
};

void menu(int n, Stack& stack)
{

	switch(n)
	{
	case 0:
		stack.freeStack();
		cout << "프로그램을 종료합니다." << endl;
		exit(0);
	case 1:
		stack.push();
		break;
	case 2:
		stack.pop();
		break;
	case 3:
		stack.search();
		break;
	case 4:
		stack.printStack();
		break;
	default:
		cout << "잘못된 입력입니다. 다시 입력해주세요" << endl;
	}
}

bool Stack::isEmpty()
{
	if (this->top == nullptr)
	{
		cout << "스택이 비어있습니다. 문장을 저장해주세요." << endl;
		return true;
	}
	else
		return false;
}

int Stack::push()
{
	cout << "저장할 문장을 입력해주세요." << endl;
	string src;
	getline(cin, src);
	Node* newNode = new Node(src);
	newNode->next = top;
	top = newNode;
	stackSize++;
	return 0;
}

void Stack::pop()
{
	if (isEmpty())
	{
		return;
	}
	Node* temp = top;
	cout << "제거된 문장: " << temp->data << endl;
	top = temp->next;
	delete temp;
	stackSize--;
}

void Stack::search()
{
	if (isEmpty())
	{
		return;
	}
	cout << "찾고 싶은 문장을 입력하세요: \n";
	string src;
	getline(cin, src);
	int i;
	Node* temp = top;
	for (i = stackSize; i > 0; --i)
	{
		if (temp->data == src)
		{
			cout << src << "는 스택의" << i << "번째에 있습니다." << endl;
			break;
		}
		temp = temp->next;
	}
	cout << src << "는 스택에 없습니다." << endl;

}

void Stack::printStack()
{
	if (isEmpty())
	{
		return;
	}

	int i;
	Node* temp = top;
	for (i = stackSize; i > 0; --i)
	{
		cout << "스택의 위치 : " << i << 
			", 저장된 단어 : " << temp->data << endl;
		temp = temp->next;
	}
}

void Stack::freeStack()
{
	while (this->top != nullptr)
	{
		pop();
	}
}


int main()
{
	Stack stack;
	while (1)
	{
		int input;
		cout << "1 : stack push , 2 : stack pop, 3 : search data, 4 : print stack, 0 : 프로그램 종료" << endl;
		cin >> input;
		getchar();
		menu(input, stack);
	}
	return 0;
}

실습 코드는 제 깃허브에 있습니다.

Workspace/자료구조 at main · cyphen156/Workspace · GitHub