[자료구조] 10. 스택 (Stack)

스택 (Stack)

▶ 쌓아놓은 더미.

▶ 특징 : LIFO (Last-In First-Out) : 후입 선출의 특징을 가짐. ≫ 가장 최근에 들어온 데이터가 가장 먼저 나감.

    ▷ Top : 스택의 상단. 정보의 입출력이 발생하는 곳.

    ▷ Bottom : 스택의 하단.

▶ 정의 : Insert와 Remove가 동일한 한 쪽 끝(Top)에서 발생하는 제한 조건(constraint)을 갖는리스트형 구조.

스택

---

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

º 객체 (Object) : 0개 이상의 아이템을 가지는 유한 선형 리스트.

º 속성 (Attributes) : 리스트의 한쪽 끝(Top)에서 삽입(Insertion)과 삭제 (Deletion) 발생.

· create(size) : 크기가 size인 empty stack 생성.
· is_full(S) : 스택 S가 가득 찼는지 검사. (즉, 스택에 아이템 추가 가능 여부 검사)
· is_empty(S) : 스택 S가 비었는지 검사. (즉, 스택에서 아이템 회수 가능 여부 검사)
  // 검사 = return 값이 TRUE or FALSE인지 확인.
· push(S, item) : 스택의 가장 위(top)에 item을 추가.
· pop(S) : 스택의 갖 위(top)에 있는 item을 삭제 및 반환. top을 하나 낮춤.
· peek(S) : 스택의 가장 위(top)에 있는 item을 반환. (삭제하지 않음) 맨 위를 체크.

▶ is_full(S)

if(the number of items is S == SIZE)
	return TRUE;
else
	return FALSE;

▶ is_empty(S)

if(the number of items in S == 0)
	return TRUE;
else
	return FALSE;

▶ push(S, item) / 넣는 것이기 때문에 인자 필요.

if(is_full(S))
	PRINT("Stack is Full")  //Error check
else
	INSERT item on the top of S;

▶ pop(S) / 빼는 것이기 때문에 인자 필요 없음.

if(is_empty(S))
	PRINT("Stack is Empty!")  //Error check

else
{
	temp <- the item on the top of S
	DELETE <- the item on the top of S
	return temp
}

▶ peek(S)

if(is_empty(S))
	PRINT("Stack is Empty!)  //Error check
    
else
	return (the item on the top of S)

---

배열을 이용한 스택의 구현

▶ 멤버 변수 2가지를 가진다. 

    ▷ 1차원 배열 stack [MAX_STACK_SIZE]

    ▷ 스택에 가장 최근에 추가한 아이템의 위치(= 배열의 인덱스)를 가리키는 top변수.

        → 정수 값이며, 초기값은 -1

▶ 가장 먼저 들어온 요소는 stack [0](맨 아래의 원소 값)에, 가장 최근에 들어온 요소는 stack [top](맨 위의 값)에 저장.

▶ 스택이 비었으면 top = -1이다.

---

▶is_empty(S) // 스택이 비었는지 확인

//Input : Stack S
//Output : Return TRUE if S is empty; otherwise return FALSE

if(top == -1)
	return TRUE

else
	return FALSE

공백 상태

▶ is_full(S) 

//Input : Stack S (size : MAX_STACK_SIZE)
//Output : Return TRUE if S is full; otherwise return FALSE

if (top == (MAX_STACK_SIZE -1)) // 배열 마지막 원소의 위치
	return TRUE
    
else
	return FALSE

포화 상태

▶ push(S, x)

//Input : S (stack), x (item to add)

if is_full(S)
	PRINT("Stack is full!")
    
else
	top <- top + 1   // top index 값을 1 증가시킨다.
	S[top] <- x  // 증가된 top index 값에 아이템을 추가한다.
    
// 순서 중요. top값이 먼저 증가된 후, 증가된 top인덱스 위치에 item을 추가한다.

push(x) 연산

 

▶pop(S)

//Input : S(stack)
//Output : the item on the top of S (when S is not empty)

if is_empty(S)
	PRINT("Stack is empty!")
    
else
	temp <- stack[top]  // top index가 가리키는 값을 임시로 저장
	top <- top - 1  // top index 값을 1 감소
	return temp  // 임시 저장한 값 반환
    
 // 순서 중요! top의 index가 가리키는 값을 반환하기 전, top의 값을 먼저 임시 저장한 후, 1만큼 감소시킨다.

pop( ) 연산

---

// 스택 초기화 함수
void init_stack(StackType* s)
{
	s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType* s)
{
	if (s->top == -1)
		return TRUE;
	else
		return FALSE;
}

// 포화 상태 검출 함수
int is_full(StackType* s)
{
	if (s->top == (MAX_STACK_SIZE - 1))
		return TRUE;
	else
		return FALSE;
}

// 삽입함수
void push(StackType* s, element item)
{
	if (is_full(s))
	{
		fprintf(stderr, "Stack is full!\n");
		return;
	}
	else
	{
		(s->top)++;
		s->data[s->top] = item;
		printf("Item %d is pushed\n", item);
	}
}

// 삭제함수
element pop(StackType* s)
{
	element temp;
	if (is_empty(s))
	{
		fprintf(stderr, "Stack is empty!\n");
		exit(1);
	}
	else
	{
		temp = s->data[s->top];
		(s->top)--;
		printf("Item %d is popped\n", temp);
		return temp;
	}
}

//top 확인 함수
char peek(StackType* s)
{
	if (is_empty(s) == TRUE)
		printf("Stack is Empty");

	else
	return s->data[s->top];
}

---

참고서적 : <C언어로 쉽게 풀어쓴 자료구조>