단일 체인 표를 이용 하여 스 택 을 실현 하 다.

스 택 은 처음부터 끝까지 만 작 동 하 는 데이터 구조 로 대열 과 반대로 스 택 의 특징 은 '선진 후 출' 이기 때문에 LIFO 라 고도 부른다.
대기 열 과 마찬가지 로 스 택 에 도 링크 와 배열 두 가지 실현 방식 이 있 는데 각자 의 장단 점 은 대기 열 을 소개 할 때 언급 한 것 과 대체적으로 같다.다음은 링크 를 사용 하여 스 택 을 실현 하 는 방식 (체인 스 택) 을 소개 합 니 다.다음은 체인 스 택 의 설명도 입 니 다.
스 택 의 특징 은 '선진 후 출' 이기 때문에 우 리 는 하나의 지침 으로 스 택 지붕 을 표시 하면 된다. 삽입 하거나 삭제 하 는 것 은 모두 상단 의 노드 를 대상 으로 하 는 것 이기 때문이다. 즉, 우 리 는 '머리 노드' 가 변화 하 는 링크 를 실현 하고 매번 변화 한 후에 머리 노드 의 최신 주 소 를 받 으 면 된다.
이 점 을 명 확 히 한 후에 단일 체인 표를 바탕 으로 조금 만 개선 하면 기본 적 인 스 택 과 대응 하 는 조작 을 실현 할 수 있다.
다음은 단일 체인 표를 이용 하여 스 택 의 소스 코드 를 실현 하 는 것 입 니 다.

#include 
#include 
#include 

using namespace std;

typedef struct stack{
	int data;
	struct stack* nextNode;
}stack_t;

static stack_t* s;

void stack_Init(stack_t** top){
	/*
	
	*/
}

bool stack_push(stack_t** top, int data){
	stack_t* node = (stack_t*)malloc(sizeof(stack_t));
	if(!node){
		return false;	
	}	
	node->data = data;
	node->nextNode = *top;
	*top = node;
	return true;
}

bool isEmpty(stack_t* top){
	return (top == NULL);
}

bool stack_pop(stack_t** top){
	if(isEmpty(*top)){
		return false;
	}
	stack_t* tmp = *top;
	*top = (*top)->nextNode;
	if(tmp){
		free(tmp);	
	}
	return true; 
}

void printStackData(stack_t* top){
	stack_t* tmp = top;
	while(tmp){
		cout << tmp->data << " ";
		tmp = tmp->nextNode;
	}
	cout << endl;
}

void stack_Deinit(stack_t** top){
	stack_t* tmp = *top;
	while(tmp){
		cout << "free node, data is:" << tmp->data << endl;
		free(tmp);
		*top = (*top)->nextNode;
		tmp =*top;
	}
}

bool topValue(stack_t* top, int& val){
	if(isEmpty(top)){
		return false;
	}
	val = top->data;
	return true;
}

int main(){
	stack_t* s = NULL;
	stack_push(&s,1);
	stack_push(&s,2);
	int val;
	if(topValue(s, val))
		cout << "now top value of stack is:" << val << endl; 
	stack_push(&s,3);
	printStackData(s);

	stack_pop(&s);
	printStackData(s);
	
	stack_push(&s,100);
	stack_push(&s,201);
	if(topValue(s, val))
		cout << "now top value of stack is:" << val << endl;
	stack_push(&s,303);
	printStackData(s);

	stack_Deinit(&s);
	printStackData(s);

	cout << "stack empty? " <<  isEmpty(s) << endl;
	
}