데이터 구조 와 알고리즘 1 스 택 의 실현

창고
우선, 우 리 는 창고 의 의 미 를 이해 해 야 한다.스 택 은 특정한 저장 소 나 레지스터 로 한쪽 은 고정 되 어 있 고 다른 한쪽 은 유동 적 이다.이 저장 소 에 저 장 된 데 이 터 는 특수 한 데이터 구조 이다.모든 데 이 터 를 저장 하거나 꺼 내 면 움 직 이 는 한 끝 (스 택 꼭대기 라 고 함) 에서 만 진행 할 수 있 고 '선진 후 출' 의 원칙 에 따라 엄 격 히 액세스 할 수 있 습 니 다. 그 중에서 있 는 요 소 는 스 택 상부 (후 입 스 택 자) 의 여러 요소 가 하나씩 이동 한 후에 야 꺼 낼 수 있 습 니 다.
2. 스 택 구조 체 의 기본 형태

typedef struct Stack{
	T* m_vect;   //         
	size_t size; //     
	size_t index;//            
}Stack;

이상 은 스 택 구조 체 의 기본 구성 부분 입 니 다.
3. 스 택 에 포 함 된 헤더 파일 구현

#include 
#include 
#include 

4. 스 택 의 주요 관련 함수

//              
void init(Stack *stack,size_t size);
// data          
void push(Stack *stack,T data);
//                           
T pop(Stack *stack);
//              
T peek(Stack *stack);
//      
bool isEmpty(Stack *stack);
//          
size_t getCnt(Stack *stack);
//        
size_t getSize(Stack *stack);
//        
bool isFull(Stack *stack);
//    
void clear(Stack *stack);
//    
void destroy(Stack *stack);
//          
void travel(Stack *stack);

5. 관련 함수 의 실현

//                    ，   T  int  
typedef int T;

//              
void init(Stack *stack,size_t size){
	stack->m_vect = calloc(size,sizeof(T));
	stack->size = size;
	stack->index = 0;
}

// data          
void push(Stack *stack,T data){
	stack->m_vect[stack->index] = data;
	stack->index++;
}

//                           
T pop(Stack *stack){
	return stack->m_vect[--stack->index];	
}

//              
T peek(Stack *stack){
	return stack->m_vect[stack->index-1];	
}

//      
bool isEmpty(Stack *stack){
	return stack->index == 0;	
}

//          
size_t getCnt(Stack *stack){
	return stack->index;	
}

//        
size_t getSize(Stack *stack){
	return stack->size;	
}

//        
bool isFull(Stack *stack){
	return stack->size == stack->index;	
}

//    
void destroy(Stack *stack){
	if(stack->m_vect != NULL){
		free(stack->m_vect);
		stack->m_vect = NULL;
	}
}
//        
void clear(Stack *stack){
	while(!isEmpty(stack)){
		pop(stack);	
	}
}
//          
void travel(Stack *stack){
	for(int i=0;iindex;i++){
		printf("%d ",stack->m_vect[i]);	
	}	
	printf("
");
}

6. 스 택 진급 기능
brr 가 arr 인지 아 닌 지 를 스 택 에 들 어 가 는 순서 로 판단 합 니 다.

bool isOutOfStack(T arr[],T brr[],size_t len){
	Stack s;
	init(&s,len);
	int j = 0;//  brr[]      
	for(int i=0;i

7. 창고 의 사용 예시

int main(){
	Stack s;
	init(&s,10);
	
	push(&s,5);
	push(&s,3);
	push(&s,2);

	int x = pop(&s);
	printf("%d
",x);
	x = pop(&s);
	printf("%d
",x);

	push(&s,10);
	x = pop(&s);
	printf("%d
",x);

	destroy(&s);


	int arr[5] = {1,2,3,4,5};
	int brr[5] = {5,4,3,1,2};
	if(isOutOfStack(arr,brr,5)){
		printf(" 
");	
	}else{
		printf(" 
");	
	}
	return 0;	
}

8. 주의사항
스 택 의 크기 가 제한 되 어 있 으 며 스 택 을 만 들 때 확 정 된 것 임 을 주의해 야 합 니 다.스 택 의 본질은 선진 적 인 후에 나 오 는 방식 에 따라 고정된 크기 의 공간 에 데 이 터 를 저장 하고 읽 는 것 이지 링크 처럼 더 큰 메모리 공간 을 신청 하여 데 이 터 를 저장 하 는 것 이 아니 라 본질 적 으로 다르다.