c언어로 쉽게 풀어쓴 자료구조 - 4장 스택
4.1 스택(stack)
스택은 모든 원소들의 삽입(insert)과 삭제(delete)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료구조이다.
스택의 특징
후입선출(LFIO : Last-In First -Out) : 가장 최근에 들어온 데이터가 먼저 나간다.
스택의 구조
스택 상단(stack top)에서만 입출력이 이루어진다.
반대쪽은 스택하단(stack bottom), 스택에 저장되는 것을 요소(element).
요소가 하나도 없을때는 공백 스택(empty stack)이라고 한다.
스택의 예) 시스템 스택을 아용한 함수 호출
시스템 스택에는 함수가 호출될 때마다 활성레코드가 만들어지며 여기에 복귀주소가 저장되고 다음과 같은 순서로 활성레코드가 만들어졌다가 없어지게 된다.
추상 자료형 스택
스택을 추상자료형으로 정의해보면 0개 이상의 요소를 가지며, 스택에 요소를 추가하거나 삭제하는 연산과 현재 스택 상태를 검사하는 연산들로 구성된다.
스택의 연산
◾push() : 스택에 데이터를 추가한다.
◾pop() : 스택에서 데이터를 삭제한다.
◾is_empty(s) : 스택이 공백상태인지 검사한다.
◾is_full(s) : 스택이 포화상태인지 검사한다.
◾create() : 스택을 생성한다.
◾peek(s) : 요소를 스택에서 삭제하지 않고 보기만 하는 연산이다.
4.2 스택의 구현
◾ 1차원 배열 stack[ ]을 이용한다.
◾ 스택에서 가장 최근에 입력되었던 자료를 가리키는 top 변수가 필요하다.
◾ 가장 먼저 들어온 요소는 stack[0]에, 가장 최근에 들어온 요소는 stack[top]에 저장된다.
◾ 스택이 공백상태이면 top은 -1이다.
is_empty, is_full 연산의 구현
스택의 top이 -1이면 스택이 비어있는 것이고,
스택의 top이 MAX_STACK_SIZE-1과 같으면 포화상태인 것이다.
push연산의 구현
스택이 가득 차있는지 is_full()을 호출하여 확인하고,
스택이 가득 차있지 않다면 top을 하나 증가시키고 요소를 삽입한다.
pop연산의 구현
스택이 비어있는지 is_empty()을 호출하여 확인하고,
스택이 비어있지 않다면 top이 가리키는 값을 반환하고 top을 하나 감소시킨다.
일반 배열 스택의 구현
구조체 안에 필요한 모든 정보를 넣고, 스택에 저장되는 요소의 타입은 element라고 가정한다.
#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_full(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) — ];
}
❼main 함수 : 스택을 정적으로 생성하였고, 함수 호출시 스택의 주소를 전달
int main(void) {
StackType s;
init_stack(&s);
push(&s, 1);
printf(“%d\n”, pop(&s));
}
4.3 동적 배열 스택의 구현
일반 배열과의 차이점은 malloc()과 realloc()을 활용하여 필요할 때마다 스택의 크기를 동적으로 늘린다는 것이다.
❶스택의 요소 정의
typedef struct {
element *data;
int capacity;
int top;
} StackType;
❷스택 초기화 함수 : 1개의 요소를 저장할수 있는 공간 확보
void init_stack(StackType *s) {
s->top = -1;
s->capacity = 1;
s->data = (element)malloc(s->capacity * sizeof(element));
}
❸포화 상태 검출 함수 : 공간 부족시 메모리를 2배 확보
int is_full(StackType *s) {
return (s->top == s->capacity);
}
❹삽입 함수
void push(StackType *s, element item) {
if (is_full(s)) {
s->capacity *= 2; s->data = (element *)realloc(s->data, s->capacity * sizeof(element));
} s->data[++(s->top)] = item;
}
4.4 스택의 응용
괄호검사 문제, 후위 표기 수식의 계산, 미로탈출 등에 활용 되고 있습니다.
