[📗c언어 쉽게 풀어쓴 자료구조4] 스택 (stack)

👑 스택이란?

: 후입선출 (Last-in First out)

• 스택 상단: 입출력 이루어지는 부분 (top)
• 스택 하단: 요소가 가장 먼저 쌓이는 부분
• 공백 스택: 스택에 요소가 하나도 없을 때

✔ 스택의 추상 자료형
1. is_sull(s): 스택이 가득 차 있는 지 확인(top==스택 사이즈)
2. is_empty(s): 스택이 비어 있는 지 확인 (top==-1)
3. push(s, item): 스택 맨 위에 item을 추가, top을 증가시키고 넣기
4. pop(s): 스택 맨 위의 요소를 제거해서 반환, 반환하고 top을 감소
5. peek(s): 스택 맨 위의 요소를 제거하지 않고 반환

👑 스택의 구현

1. 전역 변수로 구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1;

//공백 상태 검출 함수
int is_empty() {
	return (top == -1);
}

//포화 상태 검출 함수
int is_full() {
	return (top == MAX_STACK_SIZE - 1);
}

//삽입 함수
void push(element item) {
	if (is_sull()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else {
		stack[++top] = item;
	}
}

//삭제 함수
element pop() {
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else {
		return stack[top--];
	}
}

//피크 함수
element peek() {
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else {
		return stack[top];
	}
}

int main(void) 
{
	push(1);
	push(2);
	push(3);
	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("%d\n", pop());
	return 0;
}

2. 스택의 요소를 구조체로 하여 구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 100

typedef struct {
	int student_no;
	char name[MAX_STACK_SIZE];
	char address[MAX_STRING];
}element;

element stack[MAX_STACK_SIZE];
int top = -1;

//공백 상태 검출 함수
int is_empty() {
	return (top == -1);
}

//포화 상태 검출 함수
int is_full() {
	return (top == MAX_STACK_SIZE - 1);
}

//삽입 함수
void push(element item) {
	if (is_sull()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else {
		stack[++top] = item;
	}
}

//삭제 함수
element pop() {
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else {
		return stack[top--];
	}
}

//피크 함수
element peek() {
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else {
		return stack[top];
	}
}

int main(void)
{
	element ie = { 20190001, "Hong", "Seoul" };

	element oe;
	
	push(ie);
	oe = pop();
	printf("학번: %d\n", oe.student_no);
	printf("이름: %s\n", oe.name);
	printf("주소: %s\n", oe.address);
	return 0;
}

3. 관련 데이터를 함수의 매개변수로 전달 (여러 개의 스택 만들기에 용이)

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;

//스택 초기화 함수
void init_stack(StackType* s) {
	s->top = -1;
}

//공백 상태 검출 함수
int is_empty(StackType* s) {
	return (s->top == -1);
}

//포화 상태 검출 함수
int is_full(StackType* s) {
	return (s->top == MAX_STACK_SIZE - 1);
}

//삽입 함수
void push(StackType* s, element item) {
	if (is_sull(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else {
		s->data[++(s->top)] = item;
	}
}

//삭제 함수
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else {
		return s->data[(s->top)--];
	}
}

//피크 함수
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else {
		return s->data[s->top];
	}
}

int main(void)
{
	StackType s;
	init_stack(&s);
	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	return 0;
}

👑 동적 배열 스택

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
	element* data;
	int capacity;
	int top;
}StackType;

//스택 초기화 함수
void init_stack(StackType* s) {
	s->top = -1;
	s->capacity = 1;
	s->data = (element)malloc(s->capacity * sizeof(element));
}

//공백 상태 검출 함수
int is_empty(StackType* s) {
	return (s->top == -1);
}

//포화 상태 검출 함수
int is_full(StackType* s) {
	return (s->top == (s->capacity - 1));
}

//삽입 함수
void push(StackType* s, element item) {
	if (is_sull(s)) {
		(s->capacity) *= 2;
		s->data = (element*)realloc(s->data, s->capacity * sizeof(element));
	}

	s->data[++(s->top)] = item;
}

//삭제 함수
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else {
		return s->data[(s->top)--];
	}
}

//피크 함수
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else {
		return s->data[s->top];
	}
}

int main(void)
{
	StackType s;
	init_stack(&s);
	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	free(s.data);
	return 0;
}

👑 스택의 응용

: 소스코드는 쉽게 풀어쓴 c자료구조 책 참고

1. 괄호 검사 문제

: 왼쪽 괄호 만나면 스택에 삽입, 오른쪽 괄호 만나면 차례로 하나씩 꺼내서 검사. 마지막에 스택에 괄호 남아있으면, 짝이 맞지 않는 것이므로 오류

2. 후위 표기 수식의 계산

: 숫자(피연산자)는 스택에 저장. 연산자 나오면 스택에서 숫자 꺼내서 계산 후, 결괏값 다시 스택에 저장

3. 중위 표기식-> 후위 표기식

: 연산자를 스택에 저장.
: 피연산자는 출력.
: 우선순위 작거나 같은 연산자가 큰 연산자 위에 올 수 없음. (ex> 가 스택에 들어있고, +을 스택에 넣는 경우: 을 빼서 출력 후, +을 넣어줘야 함),
: 왼쪽 괄호는 무조건 스택에.
: 오른쪽 괄호-> 왼쪽 괄호 삭제될 때까지 스택에 있는 연산자들 pop

⭕ TIL (Today I learned)

& 스택 자료구조는 후입선출로, 나중에 들어간 것이 가장 먼저 나오는 자료구조이다. push에서는 top을 증가시키고 item넣기, pop에서는 반환 후 top 증가시키기. 잊지 말자!!
구조체 안에 스택 포인터(동적 할당)를 지정한 경우가 머릿속으로 잘 그려지지 않았다. 구조체 안의 스택 포인터는 동적할당할 메모리를 가리키고 있는 것이다. 즉, 스택을 가리키고 있는 것! 코드 분석할 때 머릿속으로 그리면서 생각해보자