栈

一.栈和堆

double *q=(double *)malloc(200);

*q就是栈里的，200是堆里的

动态分配的都在堆里分配，由程序员手动分配

静态分配的都在栈里分配，由系统自动分配

栈：

1.定义：

• 实现“先进后出”的存储结构

2.分类：

• 静态栈
• 动态栈：内核就是链表

3.算法

• 出栈
• 压栈

4.变量

• pTop
• pBottom

栈空：pTop==pBottom

5.应用

• 函数调用
• 中断
• 表达式求值
• 内存分配
• 缓冲处理
• 迷宫

二.代码

1.两个结构体的的定义

typedef struct Node{
	int data;
	struct Node *pNext;
}NODE,*PNODE;

typedef struct Stack{
	PNODE pTop;
	PNODE pBottom;
}STACK,*PSTACK;

👉对于Stack的理解：

Stack这个结构体里有两个成员——名字叫pTop和pBottom、类型为NODE指针

2.初始化

void init(PSTACK pS)						//传参：栈的地址
{
	pS->pTop=(PNODE)malloc(sizeof(NODE));	//给栈顶申请内存空间
	if(pS->pTop==NULL)
	{
		printf("内存分配失败！\n");
		exit(-1); 
	}
	else
	{
		pS->pBottom=pS->pTop;				//此时pT和pB指向同一个内存
		pS->pTop->pNext=NULL;				//让pT和pB指向同一个节点且该节点的指针域存放的是NULL，该节点作为一个头结点。
	}
}

3.压栈

void push(PSTACK pS,int val)
{
	PNODE pNew=(PNODE)malloc(sizeof(NODE));			//为新节点申请空间
	if(pNew==NULL)
	{
		printf("内存分配失败！\n");
		exit(-1);
	}
	else
	{
		pNew->data=val;
		pNew->pNext=pS->pTop;			
		pS->pTop=pNew;
	}
	return;
}

pNew->pNext=pS->pTop;

👆理解：

第一个元素，pNew->pNext=pS->pTop;和pNew->pNext=pS->pBottom;都可以 理解为插入的新节点的指针域和pT、pB是一样的，即指向一样，都指向头结点

但是从第二个节点开始，他的指针域存放的应该得是上一个节点的地址，对应图上的就是右边蓝色的箭头应该==左边被蓝色x覆盖的红色箭头，即pNew->pNext=pS->pTop;

4.遍历

void traverse(PSTACK pS)
{
	PNODE p=pS->pTop;
	while(p!=pS->pBottom)
	{
		printf("%d ",p->data); 
		p=p->pNext; 
	}
	return;
}

5.出栈

void pop(PSTACK pS)
{
	if(pS->pTop==pS->pBottom)
	{
		printf("栈为空！\n");
		exit(-1);
	}
	else
	{
		PNODE a=pS->pTop;
		pS->pTop=pS->pTop->pNext;
		free(a);
		a=NULL;
	}
}

这个应该也很好理解：删除a指向的节点，pTop负责往下走，防止因为删掉上面的节点而丢失下面的节点的地址

6.清空

void clear(PSTACK pS)
{
	if(pS->pTop==pS->pBottom)
	{
		printf("栈为空！\n");
		exit(-1);
	}
	else
	{
		PNODE p=pS->pTop;
		while(p!=pS->pBottom)
		{
			pS->pTop=p->pNext;
			free(p);
			p=NULL;
			p=pS->pTop;
		}
	}
}

大致思路和出栈相似，就是多了个循环，再调换一下语句顺序即可

7.完整代码

#include<stdio.h>
#include<malloc.h>
#include<stdbool.h> 
#include<stdlib.h>

typedef struct Node{
	int data;
	struct Node *pNext;
}NODE,*PNODE;

typedef struct Stack{
	PNODE pTop;
	PNODE pBottom;
}STACK,*PSTACK;

void init(PSTACK);
void push(PSTACK,int);
void traverse(PSTACK);
void pop(PSTACK);
void clear(PSTACK);
bool empty(PSTACK);


int main()
{
	STACK S;
	init(&S);
	
	push(&S,1);
	push(&S,2);
	traverse(&S);
	
	pop(&S);
	printf("\n出栈后结果为；\n");
	traverse(&S);
	
	clear(&S);
	traverse(&S);
	if(empty(&S))
		printf("清除成功！\n");
	else
		printf("清除失败！\n");
}

void init(PSTACK pS)
{
	pS->pTop=(PNODE)malloc(sizeof(NODE));
	if(pS->pTop==NULL)
	{
		printf("内存分配失败！\n");
		exit(-1); 
	}
	else
	{
		pS->pBottom=pS->pTop;
		pS->pTop->pNext=NULL;
	}
}

void push(PSTACK pS,int val)
{
	PNODE pNew=(PNODE)malloc(sizeof(NODE));
	if(pNew==NULL)
	{
		printf("内存分配失败！\n");
		exit(-1);
	}
	else
	{
		pNew->data=val;
		pNew->pNext=pS->pTop;			
		pS->pTop=pNew;
	}
	return;
}

void traverse(PSTACK pS)
{
	PNODE p=pS->pTop;
	while(p!=pS->pBottom)
	{
		printf("%d ",p->data); 
		p=p->pNext; 
	}
	return;
}

void pop(PSTACK pS)
{
	if(pS->pTop==pS->pBottom)
	{
		printf("栈为空！\n");
		exit(-1);
	}
	else
	{
		PNODE a=pS->pTop;
		pS->pTop=pS->pTop->pNext;
		free(a);
		a=NULL;
	}
}

bool empty(PSTACK pS)
{
	if(pS->pTop==pS->pBottom)
		return true;
	else
		return false;
}

void clear(PSTACK pS)
{
	if(pS->pTop==pS->pBottom)
	{
		printf("栈为空！\n");
		exit(-1);
	}
	else
	{
		PNODE p=pS->pTop;
		while(p!=pS->pBottom)
		{
			pS->pTop=p->pNext;
			free(p);
			p=NULL;
			p=pS->pTop;
		}
	}
}