[C]스택의 이해

스택

스택은 후입선출이라는 단어로 설명할  수 있습니다. 마지막에 들어온 것부터 뺀다는 뜻입니다.

박스 안에 물건을 차곡차곡 쌓는다는 표현으로 많이들 설명합니다.

 

기능으로는 

1. 삽입 push

2. 삭제 pop 

3. 반환 peek (top 위치에 있는 값만 반환)

 

상자의 가장 위에 있는 것을 top이라고 합니다.

 

push : top 위치를 하나 늘린 후 stack 배열 top 값을 입력값으로 넣어줍니다. ※코드는 이런식으로 한단 느낌

push(x){
	top = top + 1;
	stack[top] = x;
}

 pop : 현재 top 위치 값을 return 해주고 top 위치를 하나 줄여줍니다.

pop(){
	x = stack[top];
	top = top - 1; ///top의 위치 변경
    	return x;
}

peek : pop에서 top의 위치 변경만 없애주면 됩니다.

 

구조체를 사용하여 주면 스택에 들어가는 요소를 다양하게 만들 수 있습니다.

#define MAX_STACK_SIZE 100  ///스택 크기 정의

typedef int element; element 변수 자료형 통일
typedef stuct{
	element data[MAX_STACK_SIZE];
    	int top;
}Stack;

메모리 낭비를 없애기 위하여 동적할당을 이용할 수도 있습니다.

 

조금 더 자세한 코드

전역변수 구현

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

#define MAX_STACK_SIZE 100     // 스택의 최대 크기 정의
typedef int element;           // 스택에 들어가는 데이터 자료형 
element stack[MAX_STACK_SIZE]; //스택 배열
int top = -1;                  // top 값을 -1로 초기화

//공백과 포화 상태 코드 생략
void push(element x){
	top = top + 1;             // stack[++top] = x; 코드로 축소 가능
	stack[top] = x;
}
element pop(){				   //반환
	return stack[top];         //return stack[top--]; 가능 
	top = top - 1; 
}
element peek(){
	return stack[top];
}