자료구조튜터링-5.스택

스택

1. 배열

1) pop

void stack_array_pop(char *array) {
	// 가장 앞에있는 문자 제거
	for (int i = 0; i < strlen(array); i++) {
		array[i] = array[i + 1];
	}
	array[strlen(array)] = '\0'; //문자열 마지막은 NULL
}

2) push

void stack_array_push(char *array, char newChar) {
	// 가장 앞에 newChar 추가
	int len = strlen(array);
	for (int i = len; i >=0; i--) {
		array[i+1] = array[i];
	}
	array[0] = newChar;
	array[strlen(array) + 1] = '\0'; //문자열 마지막은 NULL
}

2. 연결리스트

1) pop

void stack_list_pop(list **start) { //start는 stack_list(연결리스트의 헤더포인터)의 주소를 담고있음
	//첫 노드 제거
	list *newList = (list *)malloc(sizeof(list));
	newList = *start; //stack_list값(값만 복사한 것!) 복사 start는 stack_list 가리킴
	*start = newList->link->link; //stack_list가 두 번째 노드 주소값 담게함
}

2) push

void stack_list_push(list **start, int newNum) {
	list *newList = (list *)malloc(sizeof(list));
	newList->num = newNum;
	newList->link = *start; //*start = stack_list의 값 = 첫 번째 노드의 주소
	*start = newList; //새로운 노드를 stack_list가 가리키게 함
}

전체코드

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

typedef struct list{
	int num;
	list* link;
}list;

void stack_array_pop(char *array) {
	// 가장 앞에있는 문자 제거
	for (int i = 0; i < strlen(array); i++) {
		array[i] = array[i + 1];
	}
	array[strlen(array)] = '\0'; //문자열 마지막은 NULL
}

void stack_array_push(char *array, char newChar) {
	// 가장 앞에 newChar 추가
	int len = strlen(array);
	for (int i = len; i >=0; i--) {
		array[i+1] = array[i];
	}
	array[0] = newChar;
	array[strlen(array) + 1] = '\0'; //문자열 마지막은 NULL
}

void stack_list_pop(list **start) { //start는 stack_list(연결리스트의 헤더포인터)의 주소를 담고있음
	//첫 노드 제거
	list *newList = (list *)malloc(sizeof(list));
	newList = *start; //stack_list값(값만 복사한 것!) 복사 start는 stack_list 가리킴
	*start = newList->link->link; //stack_list가 두 번째 노드 주소값 담게함
}

void stack_list_push(list **start, int newNum) {
	list *newList = (list *)malloc(sizeof(list));
	newList->num = newNum;
	newList->link = *start; //*start = stack_list의 값 = 첫 번째 노드의 주소
	*start = newList; //새로운 노드를 stack_list가 가리키게 함
}

void stack_list_print(list *start) {
	while (start != NULL) {
		printf("%d", start->num);
		start = start->link;
	}
	printf("\n");
}

int main(void) {
	// stack을 배열로 구현
	char stack_array[200] = "abcdefg"; //array로 구현할 stack
	stack_array_pop(stack_array); //stack_array에서 pop함
	for (int i = 0; i < strlen(stack_array); i++) {
		printf("%c", stack_array[i]);
	}
	printf("\n");

	stack_array_push(stack_array, 'h'); //stack_array에 h를 push함
	for (int i = 0; i < strlen(stack_array); i++) {
		printf("%c", stack_array[i]);
	}
	printf("\n");

	// stack을 연결리스트로 구현
	list* stack_list = (list *)malloc(sizeof(list)); //연결리스트 헤더포인터
	stack_list->num = 0; //처음 0번 노드
	stack_list->link = NULL;
	list* pre = (list *)malloc(sizeof(list));
	pre = stack_list;

	for (int i = 1; i < 7; i++) {
		list* p = (list *)malloc(sizeof(list));
		p->num = i; //새 노드 만들고
		p->link = NULL; //초기화시키고
		pre->link = p; //전 노드와 이어줌
		pre = p;
	}
	stack_list_pop(&stack_list); //stack_list에서 pop함
	stack_list_print(stack_list);
	stack_list_push(&stack_list, 8); //stack_list에 8을 push함
	stack_list_print(stack_list);
}