스택

개념
top 이라고 하는 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 자료구조 푸쉬(Push)와 팝(Pop)을 통해 가장 최근에 보관한 자료가 나오는 LIFO(Last In First Out)구조 후입선출 LIFO(Last In First Out)기반의 구조로 컵에 물을 붓듯이 가장 마지막에 삽입된 자료가 먼저 삭제 되는 자료구조 형태

I. 스택 (Stack)의 개요

가.  스택의 정의

- top 이라고 하는 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 자료구조

 

- 푸쉬(Push)와 팝(Pop)을 통해 가장 최근에 보관한 자료가 나오는 LIFO(Last In First Out)구조

 

 - 후입선출 LIFO(Last In First Out)기반의 구조로 컵에 물을 붓듯이 가장 마지막에 삽입된 자료가 먼저 삭제 되는 자료구조 형태

 

나.  스택의 용도

(1)   인터럽트의 처리

(2)   수식의 계산 (산술식 표현)

(3)   서브루틴의 복귀번지 저장 (함수 호출의 순서 제어)

 

Ⅱ. 스택 (Stack)의 자료구조와 연산

가. 스택의 자료구조와 연산

연산

내용

top()

스택의 맨 위에 있는 데이터 값을 반환함.

push()

스택에 데이터를 삽입함.

pop()

스택에서 데이터를 삭제함.

isempty()

스택에 원소가 없으면 ‘true’, 있으면 ‘false’ 값을 반환함.

isfull()

스택에 원소가 없으면 ‘false’, 있으면 ‘false’ 값을 반환함.

   

나. 스택의 구현

연산

C 구현

스택의 생성

/* 1 차원 배열의 사용 */

#define MAX_STACK_SIZE 100

int stack[MAX_STACK_SIZE];

/* top의 초기 값은 스택이 비어있을 때 –1이다. */

int top = -1;

push()

void push(int item){

 if(top >= MAX_STACK_SIZE - 1)

{ stack_full();

return; }

stack[++top] = item;

}

pop()

int pop( ) {

if(top == -1)

return stack_empty();

return stack[top--];

}

isempty()

int isempty(){

if( top < 0 ) return(1);

else return(0);

}

isfull()

int isfull(){

if ( top >= MAX_STACK_SIZE –1 ) return(1);

else return(0);

}

 

댓글