[자료구조] 스택

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

스택(Stack)

 

 

스택은 기본적으로 후입선출(Last In First Out)을 따른다.

스택이라는 배열에 Push()를 통해 차곡차곡 쌓아올리고

Pop()을 통해 가장 늦게 들어온 값부터 출력하는 구조이다.

 

---

 

Push()

 

Push()

 

1. 배열에서 ptr위치에 값을 넣는다.
2. ptr을 1증가시킨다.

 

 

Pop()

 

 

Pop()

 

1. ptr를 1감소시킨다.
2. 배열에서 ptr위치의 값을 출력한다.

 

---

 

소스 코드

#define __main

#ifdef __main

#include <stdio.h>

typedef struct __Stack{
	int* stk; // 스택

	int max; // 스택의 최대입력 개수
	int ptr; // 스택의 위치
} Stack;

void Init(Stack* s, int max) {
	// max크기의 스택을 할당
	s->stk = malloc(sizeof(int) * max);

	s->max = max;
	s->ptr = 0;
}

int Push(Stack* s, int x) {
	if (s->ptr >= s->max) return -1; // 스택이 가득참

	s->stk[s->ptr++] = x;

	return 0;
}

int Pop(Stack* s, int* x) {
	if (s->ptr == 0) return -1; // 스택이 비어있음

	*x = s->stk[--s->ptr];

	return 0;
}

int main() {
	Stack *s = malloc(sizeof(Stack));
	int tmp;

	Init(s, 10);

	Push(s, 4);
	Push(s, 3);

	Pop(s, &tmp);
	Pop(s, &tmp);

	s->max = s->ptr = 0;
	free(s->stk);

	return 0;
}

#endif