🌈 자료구조:: 스택(Stack)

개인 공부 과정을 기록합니다.

🚀 What I Will Learn

• 스택자료구조의 개념과 활용 방법에 대해 이해하기
• C언어를 이용해 스택 자료구조 구현하기

---

스택(Stack)

1️⃣ 스택란?

1. 스택은 한쪽으로 들어가서 한쪽으로 나오는 자료구조이다.
2. 수식 계산 등의 알고리즘에서 다방면으로 활용된다

• PUSH: 스택에 데이터 추가
• POP: 스택에 데이터 제거

---

2️⃣ 스택의 구현

1. 스택의 구현 방법에는

• 배열을 이용한 구현 방법과
• 연결 리스트를 이용한 구현 방법이 있다

1. 가장 기본적인 형태의 자료구조로, 구현 난이도는 낮은편

✔️ 배열을 이용한 스택 구현

1) 스택 선언

#include <stdio.h>
#define SIZE 10000    // 스택 크기
#define INF 99999999  //

int stack[SIZE]; // 스택 크기 선언
int top = -1;

2) 스택 삽입 함수

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

3) 스택 추출 함수

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

4) 스택 전체 출력 함수

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

5) 완성된 스택 사용하기

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

✔️ 연결리스트를 이용한 스택 구현

1) 스택 선언

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

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

2) 스택 삽입 함수

void push(Stack *stack, int data) {
  Node *node = (Node*) malloc(sizeof(Node)); node->data = data;
  node->next = stack->top;
  stack->top = node;
}

3) 스택 추출 함수

int 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;
}

4) 스택 전체 출력 함수

void show(Stack *stack) {
  Node *cur = stack->top;
  printf("--- 스택의 최상단 ---\n");

  while (cur != NULL) {
      printf("%d\n", cur->data);
      cur = cur->next;
  }
  printf("--- 스택의 최하단 ---\n");
}

5) 완성된 스택 사용하기

int main(void) {
  Stack stack;
  stack.top = NULL;
  show(&stack);
  push(&stack, 7);
  push(&stack, 5);
  push(&stack, 4);
  pop(&stack);
  push(&stack, 6);
  pop(&stack);
  show(&stack);
  system("pause");
  return 0;
}

---

✨ tl;dr

• 스택은 배열 혹은 연결 리스트를 이용해서 구현할 수 있다