데이터 구조 (2) 순서 스 택 과 체인 스 택

스 택 은 모두 가 알 고 있 듯 이 후진 이 먼저 나 가 고 스 택 의 실현 은 두 가지 가 있 는데 사실은 모두 스 택 의 조작 을 실현 하 는 것 은 실현 방식 이 다 를 뿐이다.
1. 순서 스 택: 말 그대로 안에 있 는 데 이 터 는 메모리 에서 순서대로 배열 되 어 있 습 니 다. 여러분 은 배열 을 생각 할 것 입 니 다. 맞습니다. 순서 스 택 은 배열 을 통 해 만 든 것 입 니 다.
구조 체 정의: 

typedef struct Stack
{
	int data[MAX_SIZE];    //    
	int top;               //top       ，    data    ，   -1，     ，      data[top];
}Sta;

이때 순서 스 택 의 단점 은 분명 할 것 입 니 다. data 는 최대 MAX 를 저장 합 니 다.SIZE 개 요소, 주의 하지 않 으 면 스 택 이 많아 지면 넘 칠 수 있 습 니 다.
그러나 이 배열 에서 배열 이 실현 하 는 스 택 효율 이 더욱 높 고 스 택 을 나 가 거나 스 택 에 들 어 가 는 작업 은 모두 배열 의 끝 에 이 루어 집 니 다.
2. 체인 스 택: 또는 체인 스 택 이 라 고도 부 르 는데 말 그대로 링크 잖 아!체인 헤더 의 결산 점 은 바로 top 스 택 꼭대기 이 고 데이터 도 메 인 은 스 택 꼭대기 요소 이 며 아래 지침 도 메 인 이 연결 되 어 있 습 니 다.
그러나 이렇게 되면 스 택 을 실현 하 는 것 이기 때문에 링크 의 장점, 예 를 들 어 곳곳에서 삭제 노드 를 늘 리 는 것 은 사용 할 수 없다.순서 스 택 에 비해 체인 스 택 은 스 택 이 넘 치 는 문 제 를 고려 하지 않 고 스 택 을 마음대로 눌 러 야 합 니 다. 결국은 머리 가 꽂 혀 있 기 때 문 입 니 다.
그러나 매번 창고 에 쌓 인 플러그 인 작업 은 시스템 에 메모 리 를 신청 해 야 하기 때문에 효율 이 순서 창고 보다 높 지 않다.
구조 체 정의:

typedef struct node        //  
{
	int data;
	struct node* next;
}Node;

typedef struct Stack
{
	Node *top;            //    
	int count;            //  
}Sta;

아래 에 두 스 택 코드 를 붙 이면 main 함 수 는 붙 이지 않 습 니 다.

/*
       
*/
#define MAX_SIZE 50

typedef struct Stack
{
	int data[MAX_SIZE];
	int top;
}Sta;

//   
void init(Sta *stack)
{
	stack->top = -1;
}

//  
void push(Sta *stack, int e)
{
	//       
	if(stack->top == MAX_SIZE - 1)
	{
		printf("   
");
		return ;
	}
	stack->top++;
	//printf("%d
",stack->top);
	stack->data[stack->top] = e;;
}
//    
void pop(Sta *stack)
{
	if(stack->top == - 1)
	{
		printf("  
");
	}
	stack->top--;
}
//      
int getTop(Sta *stack)
{
	if(stack->top == - 1)
	{
		printf("  
");
		return -1;
	}
	return stack->data[stack->top];
}
//display
void display(Sta *stack)
{
	int temp = stack->top;
	if(stack->top == - 1)
	{
		printf("  
");
		return;
	}
	while(temp > -1)
	{
		printf("%d
",stack->data[temp--]);
	}
}
//    
int getLength(Sta *stack)
{
	if(stack->top == - 1)
	{
		printf("  
");
		return;
	}
	return stack->top + 1;
}

/*
      
*/
typedef struct node        //  
{
	int data;
	struct node* next;
}Node;

typedef struct Stack
{
	Node *top;            //    
	int count;            //  
}Sta;

void init(Sta *stack)
{
	stack->count = 0;
	stack->top = NULL;
}
//  
void push(Sta *stack, int x)
{
	Node *new = (Node *)malloc(sizeof(Node));
	new->next = stack->top;
	new->data = x;
	stack->top = new;	
	stack->count++;
}
//  
void pop(Sta *stack)
{
	if(stack->count == 0)
	{
		printf("  
");
		return ;
	}
	Node *p = stack->top;
	stack->top = p->next;
	free(p);
	p = NULL;
	stack->count--;
}
//  
void display(Sta *stack)
{
	Node *p = stack->top;
	if(stack->count == 0)
	{
		printf("   
");
		return;
	}
	while(p != NULL)
	{
		printf("%d
",p->data);
		p = p->next;
	}
}
//      
int getTop(Sta *stack)
{
	if(stack->top == NULL)
	{
		printf("   
");
		return;
	}
	return stack->top->data;
}
//   
void clearStack(Sta *stack)
{
	if(stack->top == NULL)0
	{
		printf("   
");
		return;
	}
	Node *p = stack->top;
	Node *temp = NULL;
	while(p != NULL)
	{
		temp = p;
		p = p->next;
		free(temp);
		temp = NULL;		
	}
	stack->top = NULL;
	stack->count = 0;
}