자료구조(11)_ 연결리스트 기반 스택 구현

작성일

연결리스트 stack 코드 보기

#include<stdio.h>
#include<malloc.h>

typedef struct node
{
	int data;
	struct node * link;
}node, Stack;

 
Stack * getNode(); //노드생성함수
void push(Stack **top, int data); // 데이터 입력 함수
void pop(Stack **top); //데이터 삭제 함수
void peek(Stack **top);//데이터 출력함수 가장 위에 데이터만
void Allpeek(Stack **top); //전체 데이터 출력


int main(void)
{
	Stack * top = NULL;
	push(&top, 10);
	peek(&top);
	push(&top, 20);
	peek(&top);
	push(&top, 30);
	Allpeek(&top);
	pop(&top);
	pop(&top);
	pop(&top);
	pop(&top);
	Allpeek(&top);
	return 0;
}


Stack * getNode()
{
	Stack * tmp = (Stack *)malloc(sizeof(Stack));
	tmp->link = NULL;
	return tmp;
}


void push(Stack **top, int data)
{
	Stack * tmp = getNode();
	tmp->data = data;
	tmp->link = (*top);
	*top = tmp;
}

 

void pop(Stack **top)
{
	if ((*top) == NULL)
	{
		printf("야 없어\n");
		return;
	}
    
	Stack *tmp;
	tmp = (*top);
	(*top) = (*top)->link;
	free(tmp);
}

void peek(Stack **top)
{
	if ((*top) == NULL)
	{
		printf("DATA출력완료\n");
		return;
	}
	printf("%d",(*top)->data));
}

 
void Allpeek(Stack **top)
{
	if ((*top) == NULL)
	{
		printf("DATA출력완료\n");
		return;
	}

	printf("%d -> ", (*top)->data);
	Allpeek(&(*top)->link);
}

연결리스트 기반 스택 구현 정리

5개의 함수 존재

Stack * getNode(); // 노드생성
void push(Stack **top, int data);//데이터 입력
void pop(Stack **top);; // 데이터 삭제 함수
void peek(Stack **top);// 데이터 출력 함수 _ 가장 위에 데이터만
void Allpeek(Stack **top); //전체 데이터 출력

main을 보면 Stack *top=NULL;을 선언하다. 이 top 포인터가 top의 역할을 한다.

getNode
Stack * getNode()
{
	Stack * tmp = (Stack *)malloc(sizeof(Stack));
	tmp->link = NULL;
	return tmp;
}

tmp에 stack의 사이즈만큼 Stack 할당. 그 이후 tmp->link를 NULL로 초기화. return tmp;

Push
void push(Stack **top, int data)
{
	Stack * tmp = getNode();
	tmp->data = data;
	tmp->link = (*top);
	*top = tmp;
}

연결리스트에서는 배열처럼 index를 쓸 수가 없다. 따라서 Node를 가리키는 포인터 공간으로 top이 필요하다.

top포인터 변수가 가리키는 값이 다음에 해당하는 스택의 위치를 가리키므로. tmp->link에 (*top)을 대입하고 *top에 tmp를 넣어주면 push가 된다.

순서를 정리한다면 ①할당 ②새로운 링크 필드에 이전 노드 주소값 넣고 ③top 위치 변경

Pop
void pop(Stack **top)
{
	if ((*top) == NULL)
	{
		printf("야 없어\n");
		return;
	}
    
	Stack *tmp;
	tmp = (*top);
	(*top) = (*top)->link;
	free(tmp);
}

pop에서는 (*top)==NULL일 경우, 빠져나오도록 return을 해줘야 한다.

동적할당 하기 전에 top의 위치를 수정하면 이전에 top이 가리키던 노드에 접근할 수가 없다. 따라서 tmp를 선언후 top에 이전 노드의 주소값을 넣고 top이 top에 top이 가리키는 링크필드를 넣고 (이전 노드의 주소값이 들어있다). tmp를 해제한다.

Peek

AllPeek

void Allpeek(Stack **top)
{
	if ((*top) == NULL)
	{
		printf("DATA출력완료\n");
		return;
	}

	printf("%d -> ", (*top)->data);
	Allpeek(&(*top)->link);
}

Allpeek는 전체 데이터를 출력해주는 함수다.

재귀함수로써 (*top)->data에 해당하는 값을 출력해준다.

참고자료

kg아이티뱅크학원 (자료구조 수업)

문자열 포인터 참고 블로그

[동적할당을 이용한 문자열 처리]{https://m.blog.naver.com/PostView.nhn?blogId=kgsshow1994&logNo=140171859874&proxyReferer=https%3A%2F%2Fwww.google.com%2F}

0%