[자료구조] 스택 Stack

스택(Stack)

쌓아놓은 더미, 즉 메모리가 쌓인 더미 영역을 말합니다. 

 

스택의 특징

후입선출(LIFO:Last-In First-Out)로써 가장 최근에 들어온 데이터가 가장 먼저 나갑니다.

 

스택 추상 데이터 타입 (ADT)

객체: 0개 이상의 원소를 가지는 유한 선형 리스트

연산: 매개변수 s는 스택을 의미

 ▪ create(size)

최대 크기가 size인 공백 스택을 생성한다.

 ▪ is_full(s) 

if(스택의 원소수 == size) return TRUE;

else return FALSE;

 ▪ is_empty(s)

if(스택의 원소수 == 0) return TRUE;

else return FALSE;

 ▪ push(s, item)

if( is_full(s) ) return ERROR_STACKFULL;

else 스택의 맨 위에 item을 추가한다.

 ▪ pop(s)

if( is_empty(s) ) return ERROR_STACKEMPTY;

else 스택의 맨 위의 원소를 제거해서 반환한다.

 ▪ peek(s)

if( is_empty(s) ) return ERROR_STACKEMPTY;

else 스택의 맨 위의 원소를 제거하지 않고 반환한다.

 

배열을 이용한 스택 구현 기본 구조

변수 top은 스택에서 가장 최근에 입력되었던 자료를 가리킵니다.

가장 먼저 들어온 요소는 stack[0]에, 가장 최근에 들어온 요소는 stack[top]에 저장합니다.

스택이 공백상태라면 top은 -1 입니다.

 

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100	// 스택의 최대 크기
typedef int element;		// 데이터의 자료형
element  stack[MAX_STACK_SIZE]; // 1차원 배열
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--];
}
int main(void)
{
	push(1);
	push(2);
	push(3);
	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("%d\n", pop());
	return 0;
}

// 실행 결과
3
2
1

1차원 배열, 전역 변수를 이용한 스택 구현 프로그램입니다.

 

#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)--];
}

int main(void)
{
	StackType s;

	init_stack(&s);
	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
}

// 실행결과
3
2
1

관련 변수들을 구조체로 묶어 활용한 스택 구현 프로그램입니다.