2019-1 자료구조 수업 노트 요약 (스택)

※ 스택이란?

• 후입 선출(LIFO : Last-In First-Out)의 입출력 형태를 갖는 자료구조
• 가장 먼저 입력된 데이터가 가장 아래에 쌓이고, 가장 최근에 입력된 데이터가 가장 위에 쌓임
• 입출력이 맨 위에서만 일어나므로, 스택의 중간에서 데이터를 넣거나 지울 수 없음

※ 스택의 연산

• create() : 새로운 스택 생성
• isEmpty(stack) : 스택이 비어있는지 검사
• isFull(stack) : 스택이 가득 찼는지 검사
• push(stack, data) : 스택의 맨 위에 data를 추가
• pop(stack) : 스택의 맨 위에 있는 요소를 삭제
• peek(stack) : 스택의 맨 위에 있는 요소를 반환 (삭제 X)

※ 스택의 사용 예시

• 함수 호출에서 복귀 주소 기억
• 괄호 검사
• 후위 표기식 변환 및 연산
• 미로 탐색 등

※ C언어의 배열로 스택 구현하기

• 1차원 배열 stack[MAX_STACK_SIZE]과 가장 최근에 저장된 자료를 가리키는 변수 top을 선언
• 가장 먼저 입력된 요소는 stack[0]에, 가장 최근에 입력된 요소는 stack[top]에 저장
• top의 초기값은 -1로 설정 (C에서는 첫 번째 인덱스의 값이 0이기 때문, 만약 top이 0이라면 인덱스 0에 데이터가 있음을 의미)

★ isEmpty 연산

• top이 -1인지를 비교, top == -1이면 공백 상태로 판정

★ isFull 연산

• top이 (MAX_STACK_SIZE-1)인지를 비교, top == (MAX_STACK_SIZE-1)이면 포화 상태로 판정
• C에서는 인덱스가 0부터 시작한다는 점에 유의

★ push 연산

• 먼저, 스택이 포화 상태인지를 검사(isFull()을 호출), 가득 차 있으면 삽입 불가
• top의 값을 먼저 증가시키고 데이터를 삽입
• 만약 top의 값을 먼저 증가시키지 않으면, 가장 최근에 입력된 데이터가 지워지므로 주의!!

★ pop 연산

• 먼저, 스택이 공백 상태인지를 검사(isEmpty()를 호출), 스택이 비어있으면 삭제 불가
• top이 가리키는 값을 반환 및 삭제하고 top의 값을 하나 감소

★ C언어의 구조체를 활용한 배열 스택 코드 (main 함수는 생략)

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

// 배열 스택의 최대 크기
#define MAX_STACK_SIZE 32

typedef int elem; // int 자료형 재정의

// 스택을 구조체로 결합
typedef struct{
	elem stack[MAX_STACK_SIZE]; // 정수 스택 배열 선언
	int top; // top 변수 선언
}ArrayStack;

// 스택 초기화 함수
void init(ArrayStack *stack){
	stack->top=-1; // top을 -1로 초기화
}

// 공백 상태 검사 함수
int isEmpty(ArrayStack *stack){
	return stack->top==-1;
}

// 포화 상태 검사 함수
int isFull(ArrayStack *stack){
	return stack->top==MAX_STACK_SIZE-1;
}

// 삽입 함수
void push(ArrayStack *stack,elem item){
	if(isFull(stack)){ // 만약 스택이 가득 찼으면...
		fprintf(stderr,"스택이 가득 찼습니다.\n");
		return;
	}else stack->stack[++(stack->top)]=item; // 데이터 삽입
}

// 삭제 함수
elem pop(ArrayStack *stack){
	if(isEmpty(stack)){ // 만약 스택이 비어있으면...
		fprintf(stderr,"스택이 비어있습니다.\n");
		exit(1);
	}else return stack->stack[(stack->top)--]; // 맨 위의 값 반환 및 top 감소
}

// peek 함수
elem peek(ArrayStack *stack){
	if(isEmpty(stack)){ // 만약 스택이 비어있으면...
		fprintf(stderr,"스택이 비어있습니다.\n");
		exit(1);
	}else return stack->stack[stack->top]; // 맨 위의 값 반환
}

• 여기에서는 단순히 데이터를 정수형으로 하였음
• stack 배열과 top 변수를 하나의 구조체로 결합, 이의 포인터를 각 함수로 전달
• 스택 생성 후, init() 함수가 필요함 (top의 값을 -1로 초기화하기 위함)
• 여러 개의 스택을 만들어서 활용할 수 있음
• 여기에서 구조체의 포인터를 전달해야 한다는 점에 유의 (call by reference)