데이터 구조 - 스 택 의 링크 구현

스 택 의 링크 실현 과 배열 의 실현 원리 차이 가 많 지 않 기 때문에 링크 의 조작 을 잘 알 면 신속하게 쓸 수 있다.그러나 체인 테이블 의 실현 은 창고 가 가득 찬 문 제 를 고려 할 필요 가 없다. 왜냐하면 창고 의 크기 는 완전히 당신 이 창고 에 넣 어 결정 하기 때문이다.물론 malloc 가 신청 한 메모리 공간 은 제한 되 어 있 고 이 공간 을 초과 해도 안 됩 니 다.다음은 제 가 빈 창 고 를 만 들 고 창 고 를 쌓 으 며 창 고 를 나 가 는 작업 을 말씀 드 리 겠 습 니 다.
1. 빈 스 택 만 들 기
우선 창고 꼭대기 지침 이 창고 에 눌 릴 때 체인 테이블 하단 으로 증가 하 는 지, 위로 증가 하 는 지 를 고려한다.아래로 늘 어 나 면 스 택 을 나 갈 때 실현 할 수 없습니다. 스 택 꼭대기 지침 이 꼬리 점 을 가리 키 기 때문에 단 방향 링크 는 이전 노드 에 접근 할 수 없습니다. 양 방향 링크 를 제외 하고.스 택 을 쌓 고 스 택 을 나 가 는 작업 을 편리 하 게 하기 위해 서 머리 결산 점 이 있 는 빈 스 택 을 만 듭 니 다.
/* **    헤드 노드 가 있 는 빈 스 택 만 들 기 * /  Stack Create_Stack() {     Stack S = (Stack) malloc(sizeof(struct SNode));     S->next = NULL;     return S; }
2. 재고 관리
스 택 작업 은 실제 적 으로 새로운 결산 점 을 스 택 꼭대기 아래 에 삽입 하 는 것 이다.
void Push(Stack S, int X) {     Stack T = (Stack)malloc(sizeof(struct SNode));     T->Data = X;     T->next = S->next;            /* 창고 꼭대기 결산 점 S 에서 이동 하고 싶 습 니 다 * /      S->next = T;  } 
3. 출고
창고 에서 나 오 는 작업 은 사실상 창고 꼭대기 아래 의 결산 점 을 삭제 하 는 것 이다.
/* **    스 택 나 가기 * / int Pop (Stack S) {    Stack t = S->next;      int data ;     if(ISEmpty(S))        /* 창고 가 비 었 습 니 다. 0 * / 로 돌아 갑 니 다.    {         printf ("창고 비 움");        return 0;     }      else{         S->next = t->next;         data = t->Data;         free(t);         t = NULL;         return data;     } } 
다음은 구체 적 인 실현 코드 를 드 립 니 다.

#include 
#include 

typedef struct SNode *Stack;
struct SNode{
	int Data;
	Stack next;
};

Stack Create_Stack();
int ISEmpty(Stack S);
void Push(Stack S, int X);
int Pop(Stack S);

int main()
{
	Stack S;
	int i;
	S = Create_Stack();
	for(i=1; i<=10; i++)
		Push(S,i);
	for(; !ISEmpty(S); )
		printf("%d
",Pop(S));
}

/*
**	          
*/ 
Stack Create_Stack()
{
	Stack S = (Stack) malloc(sizeof(struct SNode));
	S->next = NULL;
	return S;
}

/*
**	     
*/
int ISEmpty(Stack S)
{
	return (S->next == NULL);
} 
/*
**	  
*/
void Push(Stack S, int X)
{
	Stack T = (Stack)malloc(sizeof(struct SNode));
	T->Data = X;
	T->next = S->next;			/*      S     */ 
	S->next = T; 
} 

/*
**	  
*/
int Pop(Stack S)
{
	Stack t = S->next; 
	int data ;
	if(ISEmpty(S))		/*   ，  0 */
	{
		printf("  
");
		return 0;
	} 
	else{
		S->next = t->next;
		data = t->Data;
		free(t);
		t = NULL;
		return data;
	}
}