컴퓨터기본/자료구조

2. Stack (Linked list)

차가운오미자 2021. 6. 14. 21:21

Stack

기본 구조

 

스택은 위에 쌓이고 위에서부터 추출된다.

 

내가 구현한 스택은 2. ArrayList 같이 배열에 저장하는 게 아니라, 한 노드에 다음 노드를 가리키는 포인터가 존재해서 쭉 이어나가는 Linked List를 사용한 스택이다.

 

1. int 데이터를 저장하는 stack

stack.h

#include <stdio.h>

#ifndef __STACK_H__
#define __STACK_H__

#define TRUE 1
#define FALSE 0

typedef int LData;

typedef struct _node {
	LData data;
	struct NODE* next; //struct 필수
}NODE;

typedef struct s_stack {
	NODE* top;
	int count;
	int size;
}MYSTACK;

MYSTACK* createStack(int s);
void push(MYSTACK* myStack, LData d); // stack size = s
LData pop(MYSTACK* myStack);
int isFull(MYSTACK* myStack);
int isEmpty(MYSTACK* myStack);
int printStack(MYSTACK* myStack);
void destroyStack(MYSTACK* myStack);

#endif

두 가지 구조체가 존재한다.

하나는 데이터를 저장할 NODE 구조체, 하나는 스택 정보를 담고 있는 MYSTACK 구조체

같은 구조체 안에 그 구조체 변수를 넣을 때는 반드시 struct 더하기! -> 이걸로 한참 고생함

 

stack.c

- 스택의 함수들 실제 구현한 소스 파일

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

#include "sstack.h"

MYSTACK* createStack(int s) {
	MYSTACK* myStack = (MYSTACK*)malloc(sizeof(MYSTACK));
	if (myStack != NULL) { //malloc 성공 여부 확인
		myStack->count = 0;
		myStack->size = s;
		myStack->top = NULL;
	}
	printf("Stack created! \n \n");
	return myStack;
}

void push(MYSTACK* myStack, LData d) {
	NODE* newNode = (NODE*)malloc(sizeof(NODE));
	if (newNode != NULL) {
		newNode->data = d;
		newNode->next = NULL;
		if (isFull(myStack)) {
			printf("The stack is full\n");
			return;
		}
		else if (isEmpty(myStack)) {
			// stack is empty
			myStack->top = newNode;
			printf("New data pushed \n");
		}
		else { // normal push
			newNode->next = myStack->top;
			myStack->top = newNode;
			printf("Data pushed in \n");
		}
		myStack->count++;
	}
}

LData pop(MYSTACK* myStack) {

	if (isEmpty(myStack)) {
		printf("The stack is empty! \n");
		return -1;
	}
	else {
		//temporary variables to save top node and its data
		NODE* temp = myStack->top;
		LData tempd = temp->data;
		// set new top as retrieving node's next;
		myStack->top = myStack->top->next;
		// free retrieving node
		free(temp);

		myStack->count--;
		return tempd;
	}
}

int isFull(MYSTACK* myStack) {
	if (myStack->count >= myStack->size) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}

int isEmpty(MYSTACK* myStack) {
	if (myStack->count == 0) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}

int printStack(MYSTACK* myStack) {
	if (isEmpty(myStack)) {
		printf("The stack is empty! \n");
		return;
	}
	NODE* tempN = myStack->top;
	printf("--- STACK PRINT --- \n");
	for (int i = 0; i < myStack->count; i++) {
		printf("data: %d \n \n", tempN->data);
		tempN = tempN->next;
	}
}

void destroyStack(MYSTACK* myStack) {
	NODE* tempN = NULL;
	while (myStack->top != NULL) {
		tempN = myStack->top;
		myStack->top = myStack->top->next;
		free(tempN);
	}
	free(myStack);
	printf("Stack destroyed! \n");
}

 

주의: malloc 시 메모리 할당 잘 됐는지 확인하기

 

main.c

- stack이 잘 구현 됐는지 확인하자

#include <stdio.h>
#include "sstack.h"

int main(void) {
    // create stack
	MYSTACK* m_Stack = createStack(5); // 사이즈 5인 스택 생성

    // push data
	push(m_Stack, 10);
	push(m_Stack, 2);
	push(m_Stack, 3);
	push(m_Stack, 7);
	push(m_Stack, 4);
	push(m_Stack, 1); // 사이즈 넘어가니까 저장하면 안됨
	printf("\n");
	printStack(m_Stack); // 잘 들어갔는지 프린트

    // pop data
	LData retrieved = pop(m_Stack); // pop시도
	printf("data retrieved: %d \n", retrieved);
	printf("\n");
	printStack(m_Stack);

    // destroy stack
	destroyStack(m_Stack);
	return 0;
}

결과:

 

2. 구조체를 data로 사용한 stack

- Student라는 객체를 담을 stack을 구현해보았다.

 

student.h

#include <stdio.h>

typedef struct student {
	char name[10];
	int age;
}Student;

void printStudent(Student* stu);
int compareStudent(Student* stu1, Student* stu2);
Student* createStudent(char* n, int a);

- ArrayList 구현에서 사용한 student.h에는 setStudent 함수를 정의했었다. main.c에서 메모리 할당한 후 그 메모리 주소레 setStudent를 이용해서 정보를 저장하는 형식이었는데, main에서 일일이 메모리 할당하는 것을 피하기 위해서 createStudent라는 함수를 만들었다.

- createStudent함수는 메모리 할당부터 변수 세팅까지 한 번에 한다.

 

student.c

#include <stdio.h>
#include <string.h>
#include "Student.h"

void setStudent(Student* stu, char* n, int a) {
	strcpy_s(stu->name, 10, n);
	stu->age = a;
}

void printStudent(Student* stu) {
	printf("name: %s, age: %d \n", stu->name, stu->age);
}

int compareStudent(Student* stu1, Student* stu2) {
	if (stu1->age == stu2->age)
		return 1;
	else
		return 0;
}
// allocate memory for Student structure, set name and age
Student* createStudent(char* n, int a) {
	Student* stu = (Student*)malloc(sizeof(Student));
	strcpy_s(stu->name, 10, n);
	stu->age = a;

	return stu;
}

 

stack.h

stack 파일들에도 미묘한 변화를 주었다.

- 기존에는 LData가 int라서 그냥 printf하고, push, pop도 자유로웠지만 이번에는 Node안에 data를 LData*로 바꾸어버렸다. 그래야 student.h 사용할 때 헷갈리지도 않는다.

- push()에서 매개변수로 받는 data또한 LData*로 바꾸어서 main에서 사용하는 Student*를 그대로 넣어줄 수 있도록 했다.

#include <stdio.h>
#include "student.h"

#ifndef __STACK_H__
#define __STACK_H__

#define TRUE 1
#define FALSE 0

typedef Student LData; //변경

typedef struct _node {
	LData* data; // 변경
	struct NODE* next;
}NODE;

typedef struct s_stack {
	NODE* top;
	int count;
	int size;
}MYSTACK;

MYSTACK* createStack(int s); // stack size = s
void push(MYSTACK* myStack, LData* d); //변경
LData* pop(MYSTACK* myStack);
int isFull(MYSTACK* myStack);
int isEmpty(MYSTACK* myStack);
int printStack(MYSTACK* myStack);
void destroyStack(MYSTACK* myStack);

#endif

 

stack.c

- pop()의 반환형도 LData* 로 바꾸어서 더 직관적

- printStack()에서 데이터가 더이상 int가 아니므로 student에 정의된 printStudent로 바꿔줬다.

- destroyStack()에서 구조체도 동적 할당 받았기 때문에 구조체도 free해준다.

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

#include "sstack.h"

MYSTACK* createStack(int s) {
	MYSTACK* myStack = (MYSTACK*)malloc(sizeof(MYSTACK));
	if (myStack != NULL) {
		myStack->count = 0;
		myStack->size = s;
		myStack->top = NULL;
	}
	printf("Stack created! \n \n");
	return myStack;
}

void push(MYSTACK* myStack, LData* d) { //변화: 매개변수 LData -> LData*
	NODE* newNode = (NODE*)malloc(sizeof(NODE));
	if (newNode != NULL) {
		newNode->data = d;
		newNode->next = NULL;
		if (isFull(myStack)) {
			printf("The stack is full\n");
			return;
		}
		else if (isEmpty(myStack)) {
			// stack is empty
			myStack->top = newNode;
			printf("New data pushed \n");
		}
		else { // normal push
			newNode->next = myStack->top;
			myStack->top = newNode;
			printf("Data pushed in \n");
		}
		myStack->count++;
	}
}

LData* pop(MYSTACK* myStack) { //변화: 반환형 LData->LData*

	if (isEmpty(myStack)) {
		printf("The stack is empty! \n");
		return;
	}
	else {
		//temporary variables to save top node and its data
		NODE* temp = myStack->top;
		LData* tempd = temp->data; //변화
		// set new top as retrieving node's next;
		myStack->top = myStack->top->next;
		// free retrieving node
		free(temp);

		myStack->count--;
		return tempd;
	}
}

int isFull(MYSTACK* myStack) {
	if (myStack->count >= myStack->size) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}

int isEmpty(MYSTACK* myStack) {
	if (myStack->count == 0) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}

int printStack(MYSTACK* myStack) {
	if (isEmpty(myStack)) {
		printf("The stack is empty! \n");
		return;
	}
	NODE* tempN = myStack->top;
	printf("--- STACK PRINT --- \n");
	for (int i = 0; i < myStack->count; i++) {
		printStudent(tempN->data); //구조체 프린트라서 구조체 함수 사용해줌
		tempN = tempN->next;
	}
	printf("\n");
}

void destroyStack(MYSTACK* myStack) {
	NODE* tempN = NULL;
	while (myStack->top != NULL) {
		tempN = myStack->top;
		myStack->top = myStack->top->next;
		free(tempN->data); //구조체도 malloc으로 할당되었기 때문에 구조체도 free
		free(tempN);
	}
	free(myStack);
	printf("Stack destroyed! \n");
}

main.c

#include <stdio.h>
#include "sstack.h"

int main(void) {

	MYSTACK* m_Stack = createStack(5);

	// stack node 안에 넣어줄 student구조체 일일이 메모리 할당 불편 -> 별개 함수로 구현
	Student* stu = createStudent("nyam", 20);
	//setStudent(stu, "nyam", 20);
	push(m_Stack, stu);

	stu = createStudent("oyam", 21);
	push(m_Stack, stu);

	stu = createStudent("pyam", 22);
	push(m_Stack, stu);

	stu = createStudent("qyam", 23);
	push(m_Stack, stu);

	stu = createStudent("ryam", 24);
	push(m_Stack, stu);

	stu = createStudent("syam", 25);
	push(m_Stack, stu);

	printf("\n");

	printStack(m_Stack);
	
	LData* retrieved = pop(m_Stack);
	printf("Data retrieved: \n  ");
	printStudent(retrieved);
	printf("\n");
	printStack(m_Stack);
	
	destroyStack(m_Stack);
	
	return 0;
}

 

결과:

 

3. 새로운 깨달음

위에 stack.c에서 pop()을 구현할 때, 반환형을 LData*로 했는데, 생각해보니 Node 안에 있는 data 구조체를 free해주지 않았다.... 그냥 냅두면 메모리가 살아있어서 나중에 문제가 될 듯! 다음 4. Queue에 있는 것처럼 LData를 반환하는 대신에, printStudent()시 주소값을 보내주는 게 맞을 것 같다. 그리고 pop() 함수 내에서 free(temp) 하기 전에 free(temp->data) 해줘야 할듯.

//stack.c
LData pop(MYSTACK* myStack) {

	if (isEmpty(myStack)) {
		printf("The stack is empty! \n");
		return;
	}
	else {
		//temporary variables to save top node and its data
		NODE* temp = myStack->top;
		LData tempd = *(temp->data); //변화
		// set new top as retrieving node's next;
		myStack->top = myStack->top->next;
		// free retrieving node
        free(temp->data); //추가
		free(temp);

		myStack->count--;
		return tempd;
	}
}

//main.c
    LData retrieved = pop(m_Stack); //changed
	printf("Data retrieved: \n  ");
	printStudent(&retrieved); //changed
	printf("\n");
	printStack(m_Stack);

 

'컴퓨터기본 > 자료구조' 카테고리의 다른 글

6. Binary Search Tree  (0) 2021.06.14
5. Doubly Linked List  (0) 2021.06.14
4. General Linear Lists  (0) 2021.06.14
3. Queue  (0) 2021.06.14
1. 재귀, ADT  (0) 2021.06.14

'컴퓨터기본/자료구조'의 다른글

  • 현재글2. Stack (Linked list)

관련글

티스토리툴바