堆疊的動態分配

靜態和動態具有很高的相似性，所有的邏輯是一致的這里就不在敘述

1>定義結構體和宣告堆疊

為堆疊分配空間時不在使用計算機內部默認連續的地址空間，使用malloc函式開辟地址記憶體空間，和靜態分配地址空間的基本操作是相同的，在結構體中定義的變數不同，在動態分配中只定義了堆疊頂和堆疊底指標

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 5

typedef struct SqStack
{
	int *top;//堆疊頂指標
	int *base;//堆疊底指標
}SqStack;//typedef重命名為SqStack

void main()
{
	SqStack S;//宣告一個堆疊
}

2>初始化堆疊

使用malloc函式分配記憶體空間，將基地址指向空間的首地址，初始化后堆疊頂和堆疊底是一致的，所以將堆疊頂初始化為堆疊底

void InitStack(SqStack &S)
{
	S.base = (int*)malloc(sizeof(int)*MaxSize);//為堆疊分配記憶體空間，不是連續的地址空間
	if (!S.base)//為空輸出提示
		printf("抱歉記憶體分配失敗!");
	else
		printf("記憶體分配完成，初始化成功!\n");
	S.top = S.base;//初始堆疊堆疊頂等價于堆疊底，講堆疊頂初始化為堆疊底
}

這樣堆疊初始化完成，同時基地址也指向了開辟空間的首地址（也就是堆疊底）

3>添加資料

輸入資料如果輸入資料數量n：

n>maxsize 則輸入是不能完成全部是輸入

n<maxsize 可以完成所有輸入

這里使用兩種輸入是可以更好理解堆疊輸入程序中記憶體空間的可用度:

更好的簡潔的方式可以（s.top-s.base==maxsize）判斷空間是否滿 *(s.top)++=e;先將資料壓入堆疊然后指標移動位置，這樣可以節省很多代碼，上述方法便于理解

void CreatStack(SqStack &S,int n)
{
	int data;//保存資料
	printf("向堆疊中添加%d個資料：\n", n);
	if (n <= MaxSize)
	{
		for (int i = 0; i < n ; i++)
		{
			printf("data[%d]=", i);
			scanf("%d", &data);
			*S.top++ = data;//先賦值后移動位置
		}
	}
	else
	{
		for (int i = 0; i < MaxSize ; i++)
		{
			printf("data[%d]=", i);
			scanf("%d", &data);
			*S.top++= data;//先賦值后自增位置
		}
		printf("剩余%d元素無法入堆疊!\n",n-MaxSize);
	}
}

輸入資料數量小于開辟的記憶體空間

輸入資料數量大于開辟的記憶體空間

4>輸出資料

在輸入中在完成最后一個資料是輸入程序中，是先賦值給地址空間然后指標后移動，所以在輸入資料結束后，指標其實在堆疊頂的上方（在輸入資料是可以修改到堆疊頂這里就沒有修改），在輸出是資料前進行指標前移

void ShowStack(SqStack S)//列印
{
	printf("列印堆疊資料:\n");
	int i = 0;
	while (S.top != S.base)
	{
		S.top--;//從堆疊頂向下移動
		printf("data[%d]=%d\n", i, *S.top);
		i++;
	}
}

輸入資料空間小于開辟空間:

輸入資料空間大于開辟空間

5>插入資料到堆疊頂

插入資料到堆疊頂需要判斷堆疊的空間是否充足，只有具備剩余空間條件下才可以插入，由于在輸入資料中末資料輸入后指標以及在節點的上方，所以插入堆疊頂時先賦值后移動指標

void PushStack(SqStack &S, int e)//將元素入堆疊
{
	if (S.top - S.base ==MaxSize)
		printf("當前堆疊已滿!\n");
	*S.top++ = e;//賦值后移動節點到下一處
}

向堆疊頂插入資料

6>洗掉堆疊頂元素

同理由于在輸入資料中末資料輸入后指標以及在節點的上方，所以洗掉堆疊頂時先移動指標后賦值

void  PopStack(SqStack &S)//元素出堆疊
{
	int e=*(S.top--);//保存堆疊頂資料
	printf("洗掉堆疊頂元素%d\n",e);
}

先插入然后立即洗掉

常規輸入洗掉堆疊頂元素

7>獲取堆疊頂元素

由于在輸入資料時末資料指標的位置，所以和洗掉堆疊頂一樣先移動指標后獲取資料，

void  GetElemStack(SqStack S)//得到堆疊頂元素
{
	S.top--;
	int e = *S.top;
	printf("堆疊頂元素為%d\n", e);

}

8>整體代碼

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 5

typedef struct SqStack
{
	int *top;//堆疊頂指標
	int *base;//堆疊底指標
}SqStack;//typedef重命名為SqStack

void InitStack(SqStack &S)
{
	S.base = (int*)malloc(sizeof(int)*MaxSize);//為堆疊分配記憶體空間，不是連續的地址空間
	if (!S.base)//為空輸出提示
		printf("抱歉記憶體分配失敗!");
	else
		printf("記憶體分配完成，初始化成功!\n");
	S.top = S.base;//初始堆疊堆疊頂等價于堆疊底，講堆疊頂初始化為堆疊底
}

void EmptyStack(SqStack S)
{
	if (S.top==S.base)
		printf("當前為空堆疊!\n");
	else
		printf("當前堆疊不為空堆疊!\n");
}

void CreatStack(SqStack &S,int n)
{
	int data;//保存資料
	printf("向堆疊中添加%d個資料：\n", n);
	if (n <= MaxSize)
	{
		for (int i = 0; i < n ; i++)
		{
			printf("data[%d]=", i);
			scanf("%d", &data);
			*S.top++ = data;//先賦值后移動位置
		}
	}
	else
	{
		for (int i = 0; i < MaxSize ; i++)
		{
			printf("data[%d]=", i);
			scanf("%d", &data);
			*S.top++= data;//先賦值后自增位置
		}
		printf("剩余%d元素無法入堆疊!\n",n-MaxSize);
	}
}

void PushStack(SqStack &S, int e)//將元素入堆疊
{
	if (S.top - S.base ==MaxSize)
		printf("當前堆疊已滿!\n");
	*S.top++ = e;//賦值后移動節點到下一處
}

void  PopStack(SqStack &S)//元素出堆疊
{
	int e=*(S.top--);//保存堆疊頂資料
	printf("洗掉堆疊頂元素%d\n",e);
}

void  GetElemStack(SqStack S)//得到堆疊頂元素
{
	S.top--;
	int e = *S.top;
	printf("堆疊頂元素為%d\n", e);

}

void ShowStack(SqStack S)//列印
{
	printf("列印堆疊資料:\n");
	int i = 0;
	while (S.top != S.base)
	{
		S.top--;//從堆疊頂向下移動
		printf("data[%d]=%d\n", i, *S.top);
		i++;
	}
}

void main()
{
	SqStack S;//宣告一個堆疊
	InitStack(S);//初始化
	EmptyStack(S);//判斷是否空堆疊
	CreatStack(S,4);//添加資料
	PushStack(S,99);//將元素插入到堆疊頂
	PopStack(S);//將堆疊頂資料洗掉
	GetElemStack(S);//得到堆疊頂元素
	ShowStack(S);//輸出堆疊資料
}