数据结构--栈

#include <iostream>
#include <malloc.h>
#include<conio.h>

//定义节点
typedef char ElemType;
typedef struct Node{
	ElemType data;			
	struct Node *next;	
} Stack;

/*
*栈S指向一个没有数据的节点
*/
void Init(Stack *&S){
	S=(Stack *)malloc(sizeof(Stack));//分配头结点
	S->next=NULL;
}

/*
*销毁栈
*/
void Destroy(Stack *&S){
	Stack *p=S->next;
	while (p!=NULL){
		free(S);
		S=p;
		p=p->next;
	}
}

int Length(Stack *s){
	int i=0;
	s=s->next;
	while (s!=NULL){
		i++;s=s->next;
	}
	return i;
}

int StackEmpty(Stack *s){
	return(s->next==NULL);
}

/*
*将数据压栈,压到头结点下面
*/
void Push(Stack *&S,ElemType e){
	Stack *p=(Stack *)malloc(sizeof(Stack));
	p->data=e;
	p->next=S->next;
	S->next=p;
}

/*
*数据出栈，出栈的数据放在e里面
*/
int Pop(Stack *&S,ElemType &e){
	Stack *p;
	if (S->next==NULL)		//栈空的情况
		return 0;
	p=S->next;				//p指向第一个数据结点
	e=p->data;
	S->next=p->next;
	free(p);
	return 1;
}

/*
*获取顶端数据，数据放在e里面
*/
int GetTop(Stack *S,ElemType &e){
	if (S->next==NULL)
		return 0;
	e=S->next->data;
	return 1;
}

void Display(Stack *S){
	S=S->next;
	while (S!=NULL){
		std::cout<<S->data;
		S=S->next;
	}
	std::cout<<std::endl;
}

int main(){
	Stack *L;
	char e;
	Init(L);
	Push(L,'a');
	Push(L,'b');
    Display(L);
	Pop(L,e);
	std::cout<<e<<std::endl;
	Display(L);
	Push(L,'c');
	Display(L);
	Pop(L,e);
	Pop(L,e);
	Display(L);
	Push(L,'d');
	Display(L);
	getche();
	return 1;
}

 运行结果：

ba

b

a

ca

 

d