스택이란?
데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다.
스택에서의 입출력은 맨 위에서만 일어나며, 스택의 중간에서 데이터를 삭제할 수 없습니다.
그렇기 때문에 후입선출이라는 특징을 가지고 있습니다.
LIFO (Last In First Out) 후입선출
스택 용어
Stack Top - 스택 상단
Stack Bottom - 스택 하단
element - 스택에 저장되는 요소
empty Stack - 요소가 하나도 없는 공백 상태의 스택
스택의 구현
stack[ ] 배열에 스택의 요소들을 저장한다고 가정했을 때,
스택에 가장 최근 입력된 자료를 가리키는 top 변수가 필요하며
가장 먼저 들어온 요소는 stack[0] 에
가장 최근에 들어온 요소는 stack[top] 에 저장된다.
스택의 연산
공백상태 검사
스택에 자료를 삭제할 때는 스택이 공백상태인지 검사 후 자료를 삭제해야 한다.
공백상태인지 검사할 때에는 top 이 -1 인지 비교하면 된다.
알고리즘)
s_empty(S) :
if top == -1
then return TRUE
else return FALSE
포화상태 검사
스택에 자료를 삽입할 때는 스택이 포화상태인지 검사 후 자료를 추가해야 한다.
포화상태인지 검사할 때에는 top 을 (MAX_STACK_SIZE -1 ) 과 비교하여 같으면 포화상태로 인정한다.
배열의 인덱스는 0부터 시작하기 때문에 -1 을 해주어야 한다.
알고리즘)
is_full(S):
if top >= (MAX_STACK_SIZE - 1)
then return TRUE
else return FALSE
스택에 자료 삽입
위에서 설명한 것과 같이 is_full() 함수를 호출하여 스택이 포화상태인지 검사한다.
포화상태일 경우 overflow error 을 띄우고
아닐 경우 스택의 상단 (top) 에 자료를 추가한다.
알고리즘)
push(S, x):
if is_full(S)
then error "overflow"
else top <- top+1
stack[top] <- x
스택에 자료 삭제
삭제 역시 is_empty() 함수를 호출하여 스택이 공백상태인지 검사한다.
공백상태일 경우 에러 메세지를 출력하고
아닐 경우 top 이 가리키는 값을 반환하고 top 을 하나 감소시킨다.
알고리즘)
pop(S, x):
if is_empty(S)
then error "underflow"
else e <- stack[top]
top <- top -1
return e
스택의 연산 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100 // 스택의 최대 크기
typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1;
// 공백 상태 검출 함수
int is_empty() {
return (top == -1);
}
// 포화 상태 검출 함수
int is_full() {
return (top == (MAX_STACK_SIZE - 1));
}
// 삽입 함수
void push(element item) {
if (is_full()) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
else stack[++top] = item;
}
// 삭제함수
element pop() {
if (is_empty()) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return stack[top--];
}
void print_stack() {
if (is_empty()) {
printf("스택 공백 상태\n");
return;
}
printf("현재 스택 상태: ");
for (int i = 0; i <= top; i ++ ) {
printf("%d ", stack[i]);
}
printf("\n");
}
int main(void) {
push(1);
push(2);
push(3);
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
printf("\n");
printf("============================\n");
printf("\n");
printf("3번 pop() 함수 호출 후\n");
print_stack();
return 0;
}
결과)
'Computer Science' 카테고리의 다른 글
자료구조 - 큐 (원형큐) (0) | 2023.12.01 |
---|---|
자료구조 - 큐 (선형큐) (0) | 2023.11.27 |
자료구조 - 선형자료구조 (연결리스트) (2) | 2023.09.23 |
자료구조 - 복잡도 (0) | 2023.09.22 |