[C언어] 스택

1. 스택

• 스택은 한쪽으로 들어가서 한쪽으로 나오는 자료구조

  push: 스택에서 데이터를 넣는다.
  pop: 스택에서 데이터를 뺀다.
  top: 스택의 입구(최상단)

1) 배열을 이용한 스택 구현

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h> 
#include <stdlib.h>
#define SIZE 10000
#define INF 99999999

int stack[SIZE];
int top = -1; // top : 스택의 입구(최상단)

void push(int data) {
	if (top == SIZE - 1) {
		printf("스택 오버플로우가 발생했습니다.\n");
		return;
	}
	stack[++top] = data;
}

int pop() {
	if (top == -1) {
		printf("스택 언더플로우가 발생했습니다.\n");
		return -INF;
	}
	return stack[top--];
}

void show() {
	printf("--- 스택의 최상단(입구) ---\n");
	for (int i = top; i >= 0; i--) {
		printf("%d\n", stack[i]);
	}
	printf("--- 스택의 최하단 ---\n");
}

int main(void) {
	push(7);
	push(5);
	push(4);
	pop();
	push(6);
	pop();
	show();
	system("pause");
	return 0;
}

2) 연결 리스트를 이용한 스택 구현

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h> 
#include <stdlib.h>
#define INF 99999999

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

typedef struct {
	Node* top;
} Stack;

void push(Stack* stack, int data) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = stack->top; // 삽입할 노드의 next는 현재 스택의 top
	stack->top = node; // 새로운 스택의 top은 삽입할 노드
}

void pop(Stack *stack) {
	if (stack->top == NULL) {
		printf("스택 언더플로우가 발생했습니다.\n");
		return -INF;
	}
	Node* node = stack->top;
	int data = node->data;
	stack->top = node->next;
	free(node); // 할당 해제
	return data;
}

void show(Stack* stack) {
	Node* cur = stack->top;
	printf("--- 스택의 최상단(입구) ---\n");
	while(cur != NULL) {
		printf("%d\n", cur->data);
		cur = cur->next;
	}
	printf("--- 스택의 최하단 ---\n");
}

int main(void) {
	Stack s;
	s.top = NULL;
	push(&s, 10); // 스택변수의 메모리 주소를 보내줘야함
	push(&s, 3);
	push(&s, 7);
	pop(&s);
	push(&s, 8);
	pop(&s);
	show(&s);
	system("pause");
	return 0;
}

2. 계산기 만들기