数据结构（五）——链栈

栈——链栈

链栈

​ 链栈是一种特殊的线性链表，使使用链式存储结构的栈，链栈也有栈顶栈底，同样是一种后进先出（LIFO）的数据结构

链栈定义

​ 链栈需要定义两个结构体，LinkStackNode 用来定义链栈节点的类型，存放节点的数据和下一节点的 next 指针

​ LinkStack 结构体用来定义链栈的结构，存放 top 栈顶指针和链栈的总长度

typedef struct LinkStackNode {
	int data;
	LinkStackNode *next;
}LinkStackNode;

typedef struct LinkStack {
	LinkStackNode *top;
	int length;
}LinkStack;

创建链栈

​ 创建链栈的过程就是定义 LinkStack 变量并为其分配内存，再让栈顶指针指空，栈的长度归 0

LinkStack * CreateStack() {
	LinkStack *p;
	p = (LinkStack *)malloc(sizeof(LinkStack));
	p->length = 0;
	p->top = NULL;
	return p;
}

判断栈是否为空

int IsEmpty(LinkStack *p) {
	if (p->length == 0)
		return 1;
	else
		return 0;
}

入栈

​ 因为栈的本质是一种后入先出的数据结构，所以所有的操作都要在栈顶进行。入栈操作即定义新的 LinkStackNode 并为其分配内存，给他的数据域赋值，使新节点的 next 指向原栈顶处的节点，在使新入节点成为新的栈顶结点，栈的长度 +1

LinkStack *PushStack(LinkStack *p, int d) {
	if (p == NULL)
		return NULL;
	LinkStackNode *temp;
	temp = (LinkStackNode *)malloc(sizeof(LinkStackNode));
	temp->data = d;
	temp->next = p->top;
	p->top = temp;
	p->length++;
	return p;
}

出栈

​ 出栈需要先判断栈是否为空，再将栈顶指针指向原栈顶节点的 next，释放原栈顶节点的内存，栈的长度 -1

LinkStack *PopStack(LinkStack *p) {
	LinkStackNode *temp;
	temp = p->top;
	if (p->top == NULL || IsEmpty(p) == 1) {
		cout << "this stack is EMPTY !" << endl;
		return p;
	}
	else {
		p->top = p->top->next;
		free(temp);
		p->length--;
		return p;
	}
}

打印栈

​ 打印栈同样先检测栈是否为空，然后在遍历栈的同时打印每个节点的数据

int ShowStack(LinkStack *p) {
	LinkStackNode *temp;
	temp = p->top;
	if (p->top == NULL || IsEmpty(p) == 1) {
		cout << "this stack is EMPTY !" << endl;
		return 0;
	}
	while (temp != NULL) {
		cout << temp->data << ' ';
		temp = temp->next;
	}
	cout << endl;
	return 0;
}