스택(Stack)

스택이란?

사진 출처 : https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

• Stack : (보통 깔끔하게 정돈된) 무더기[더미] (출처 : 네이버 영어사전)
• 후입선출(LIFO : Last in First out) 또는 선입후출(FILO : First in Last out)의 방식을 사용하는 자료구조
• 데이터의 삽입과 삭제가 한쪽 방향에서만 일어난다.

스택의 연산

• push(s, item) : 스택에 데이터를 추가
• pop(s) : 스택 최상단 데이터를 반환하고 삭제
• is_full(s) : 스택 포화상태 검사
• is_empty(s) : 스택 공백상태 검사
• peek(s) : 스택 최상단 데이터를 반환, 삭제X

스택 사용 예시

• 어떤 함수가 자기 자신을 다시 호출할 때 복귀 주소를 시스템 스택에 저장하고 호출되는 함수를 위한 매개변수 및 지역변수를 스택으로부터 할당받는다.
• 중위표기식을 후위표기식으로 변환할 때 스택을 사용한다.

---

배열을 이용한 스택 구현

#define STACK_SIZE 100
int stack[STACK_SIZE];
int idx = -1;
void push(char value) {
	stack[++idx] = value;
}
int pop() {
	if (idx < 0) return -1;
	else return stack[idx--];
}
int is_full() {
	if (top == (STACK_SIZE - 1)) return 1;
	else return 0;
}
int is_empty() {
	if (size() == 0) return 1;
	else return 0;
}
int peek() {
	if (!is_empty()) return stack[idx];
}

연결리스트를 이용한 링크드 스택 구현

연결리스트를 사용하기 때문에 배열을 사용한 스택과 달리 오버플로우가 발생하지 않는다.

typedef struct Node {
	int data;
	struct Node* link;
} Node;
typedef struct {
	Node* top;
	int count;
} Stack;
void init_stack(Stack* stack) {
	stack->top = NULL;
	stack->count = 0;
}
int is_empty(Stack* stack) {
	return stack->count == 0;
}
void push(Stack* stack, int data) {
	Node* now = (Node*)malloc(sizeof(Node));
	now->data = data;
	now->link = NULL;
	now->link = stack->top;
	stack->top = now;
	stack->count++;
}
int pop(Stack* stack) {
	if (is_empty(stack)) {
		return -1;
	}
	Node* now = stack->top;
	int re = now->data;
	stack->top = now->link;
	free(now);
	stack->count--;
	return re;
}
int peek(Stack* stack) {
	if (is_empty(stack)) return -1;
	else return stack->top->data;
}