자료구조 - 스택

스택이란?

데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다.

 

스택에서의 입출력은 맨 위에서만 일어나며, 스택의 중간에서 데이터를 삭제할 수 없습니다.

그렇기 때문에 후입선출이라는 특징을 가지고 있습니다.

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

 

 

결과)